53. Maximum Subarray

This is classic kadane's algorithm. Let dp[i] be the maximum sum of a continuos subarray. So the state transition is shown as following:

dp[i] = max(dp[i-1]+nums[i], nums[i])

At the end, we get the maximum sum in the dp[i].

1:  class Solution {  
2:  public:  
3:    int maxSubArray(vector<int>& nums) {  
4:      int n = nums.size();  
5:      if (n == 0) return 0;  
6:      vector<int> dp(n, INT_MIN);  
7:      int maxSum = nums[0];  
8:      dp[0] = nums[0];  
9:      for (int i = 1; i < nums.size(); i++) {  
10:        dp[i] = max(dp[i-1]+nums[i], nums[i]);  
11:        maxSum = max(dp[i], maxSum);  
12:      }  
13:      return maxSum;  
14:    }  
15:  };