53. Maximum Subarray

解題思路

當探訪下一個 array 中的 element 時，要選擇把最大 subarray 的範圍包含進該 element，還是說以該 element 為起點重新計算？

決定完後，再把 element 值更新為當前最大 subarray 的總和值。

程式碼

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