53. Maximum Subarray

1.問題

• 給予一個整數的array, 找出總和為最大值的連續subarray

2.想法

• 提問

  • 確認題意: 取得最大總和的subarray

• parameter

  • number list

• test input

• 說明想法

  • 由左邊開始移動, 計算subarray的總和

  • 記錄歷史的最大總和

  • 一旦總和小於0, 則讓總和歸零

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0], i, j, sum=0;
        for(i = 0;i< (int)nums.size(); i++){
            sum += nums[i];
            ans = max(sum,ans);
            sum = max(sum,0);
        }
        return ans;
    }
};