# Leetcode 53. Maximum Subarray
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/maximum-subarray/ 。

想法 :

不能O(n^2)，要找O(n)的算法，陣列代表的狀態就是目前為止的最大連續和。
採用Kadane's algorithm。狀態轉移為選前綴和或是不選。
選了就把前綴和加上自己，不選就是自己一個元素，如果小於0就以0儲存。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp[100010]={0},l=nums.size(),maxn=-10010,sum=0;
        
        for(int i=0 ; i<l ; i++){
            sum+=nums[i];
            
            dp[i]=max(nums[i],sum);
            if(sum<0) sum=0;
        }
        
        for(int i=0 ; i<l ; i++){
            maxn=max(maxn,dp[i]);
        }
        
        return maxn;
    }
};