原題
Description
Given an array of integers, find a contiguous subarray which has the largest sum.
Notice
The subarray should contain at least one number.
Example
Given the array [?2,2,?3,4,?1,2,1,?5,3], the contiguous subarray [4,?1,2,1] has the largest sum = 6.
解題
動態(tài)規(guī)劃問題颅悉，很容易可以得到狀態(tài)轉移方程：
dp[i] = MAX( dp[i - 1], dp[i - 1] + A[i] )
因為實際上只會用到上一次的狀態(tài)碧库，所以只需要一個變量（而不是數組）即可存儲。
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
// write your code here
if (nums.size() <= 0) return 0;
int ans = INT_MIN, sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
ans = max(ans, sum);
// 當sum<0時 要置位0 意味著拋棄前i個數 從i+1開始計算
sum = max(0, sum);
}
return ans;
}
};
拓展
采用分治法解決。
假如我們將數組二分，那么最優(yōu)解有三種情況
- 最優(yōu)解在左子數組
- 最優(yōu)解在右子數組
- 最優(yōu)解跨越了左右子數組
前兩種情況比較容易解決，第三種情況的做法就是從分割點開始向兩邊掃描，得出該種情況的最優(yōu)解。
最后將三種情況的解比較得出最優(yōu)解闻镶。
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
// write your code here
if (nums.size() <= 0) return 0;
int ans = INT_MIN, sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
ans = max(ans, sum);
sum = max(0, sum);
}
return ans;
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
// 獲得情況一的最優(yōu)解
int leftMax = helper(nums, left, mid - 1);
// 獲得情況二的最優(yōu)解
int rightMax = helper(nums, mid + 1, right);
// 從分割點向兩邊掃描，獲得情況三的最優(yōu)解
int midMax = nums[mid], sum = midMax;
for (int i = mid - 1; i >= left; i--) {
sum += nums[i];
midMax = max(midMax, sum);
}
sum = midMax;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
midMax = max(midMax, sum);
}
// 比較三種情況 獲得最優(yōu)解
return max(leftMax, max(midMax, rightMax));
}
};
