Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
the contiguous subarray
Analysis:
This is typical DP problem. Let D[i] be the maximum subarray that ends at index i. Then, D[i+1] = max(D[i] + nums[i], nums[i]).
Max(D[i]) will be the result.
[−2,1,−3,4,−1,2,1,−5,4]
,the contiguous subarray
[4,−1,2,1]
has the largest sum = 6
.int maxSubArray(vector<int>& nums) { int len = nums.size(); if(0 == len) return 0; vector<int> rec(len,0); rec[0] = nums[0]; for(int i=1;i<len;i++) { rec[i] = max(rec[i-1] + nums[i], nums[i]); } return *max_element(rec.begin(), rec.end()); }Look at the code. Actually, the max subarray can be obtained from the adjacent elements
int maxSubArray(vector<int>& nums) { int len = nums.size(); if(0 == len) return 0; int maxSub = nums[0]; int res = maxSub; for(int i=1;i<len;i++) { maxSub = max(nums[i] + maxSub, nums[i]); res = max(maxSub, res); } return res; }