Leetcode 53. Maximum Subarray

53. Maximum Subarray

Total Accepted: 123212
Total Submissions: 331027
Difficulty: Medium

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路：DP中的子序列和最大化问题。

可见https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input

代码：

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int i,n=nums.size(),curmax=nums[0],resmax=nums[0];
 5         for(i=1;i<n;i++){
 6             curmax=max(nums[i],curmax+nums[i]);
 7             resmax=max(resmax,curmax);
 8         }
 9         return resmax;
10     }
11 };