# 53. Maximum Subarray

[leetcode網址](https://leetcode.com/problems/maximum-subarray/description/)

## 問題
找出一個子陣列，且此子陣列的數值總和是最大的，回傳這個最大值

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
        The subarray [4,-1,2,1] has the largest sum 6.

## Idea
又是一題Kadane's algorithm，這次是keep一個`sum`和一個最大值`maxi`
- `sum`: 不斷的累加數值，如果小於0，就變成0重新開始累加數值
- `maxi`: 再迭代陣列過程中更新目前最大值

## Solution
時間複雜=O(N)；空間複雜度=O(1)

int maxSubArray(vector<int>& nums) {
    int maxi= INT_MIN, sum=0;

    for(auto&num: nums){
        sum+=num;
        maxi = max(maxi, sum);
        if(sum<0)sum=0;
    }

    return maxi;
}