## [53\. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

Kadane's Algorithm

對於新的元素有兩個選擇：
- 選：`curSum + num`
- 不選：`num`

:::spoiler Solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curSum = 0;
        int maxSum = INT_MIN;
        for (int num : nums)
        {
            curSum = max(num, curSum + num);
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::