給定一個整數(shù)數(shù)組椭更，找到一個具有最大和的子數(shù)組，返回其最大和饶深。
樣例
給出數(shù)組[?2,2,?3,4,?1,2,1,?5,3]餐曹，符合要求的子數(shù)組為[4,?1,2,1]，其最大和為6
挑戰(zhàn)
要求時間復(fù)雜度為O(n)
解答
int maxSubArray(vector<int> &nums) {
int maxSum = nums[0];
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (sum < 0) {
sum = 0;
maxSum = nums[i] > maxSum ? nums[i] : maxSum;
} else {
maxSum = sum > maxSum ? sum : maxSum;
}
}
return maxSum;
}
擴(kuò)展
描述
給定一個整數(shù)數(shù)組敌厘，找出兩個 不重疊 子數(shù)組使得它們的和最大台猴。
每個子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的。
返回最大的和俱两。
子數(shù)組最少包含一個數(shù)
樣例
給出數(shù)組 [1, 3, -1, 2, -1, 2]
這兩個子數(shù)組分別為 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]饱狂，它們的最大和都是 7
挑戰(zhàn)
要求時間復(fù)雜度為 O(n)
方法一：
以第i個元素為邊界，將數(shù)組分為前后兩部分宪彩，分別計(jì)算前一部分和后一部分的最大子數(shù)組和休讳，再將兩個和相加，最后從這些和里面找到一個最大的和
這種解法每一種情況的復(fù)雜度數(shù)O(N)尿孔，N-1種情況的復(fù)雜度為O(N^2)俊柔。
int maxTwoSubArrays(vector<int> &nums) {
int maxSum;
for (int i = 0; i < nums.size() - 1; i++) {
int preMax = maxSubArray(nums, 0, i);
int index = i + 1 < nums.size() ? i + 1 : nums.size() - 1;
int postMax = maxSubArray(nums, index, nums.size() - 1);
int sum = preMax + postMax;
if (i == 0) {
maxSum = sum;
} else {
maxSum = sum > maxSum ? sum : maxSum;
}
}
return maxSum;
}
int maxSubArray(vector<int> &nums, int begin, int end) {
int maxSum = nums[begin];
int sum = 0;
for (int i = begin; i <= end; i++) {
sum += nums[i];
if (sum < 0) {
sum = 0;
maxSum = nums[i] > maxSum ? nums[i] : maxSum;
} else {
maxSum = sum > maxSum ? sum : maxSum;
}
}
return maxSum;
}
方法二：采用動態(tài)規(guī)劃的思想
方法一中的每種情況都存在重復(fù)計(jì)算的情況筹麸，考慮使用空間換時間的方案，將計(jì)算的中間結(jié)果保存下來
創(chuàng)建兩個數(shù)組雏婶，pre[i]記錄前一部分0~i時的最大的子數(shù)組和物赶，post[i]記錄后一部分的最大子數(shù)組和，通過求最大的pre[i] + post[size - i - 1]得到最大的和留晚。
int maxTwoSubArrays(vector<int> &nums) {
vector<int> pre;
maxPreSubArrays(nums, pre);
vector<int> post;
maxPostSubArrays(nums, post);
int maxSum = pre[0] + post[pre.size() - 1];
for (int i = 0; i < pre.size(); i++) {
int sum = pre[i] + post[pre.size() - 1 - i];
maxSum = sum > maxSum ? sum : maxSum;
}
return maxSum;
}
int maxPreSubArrays(vector<int> &nums, vector<int> &pre) {
int maxSum = nums[0];
int sum = 0;
for (int i = 0; i < nums.size() - 1; i++) {
sum += nums[i];
if (sum < 0) {
sum = 0;
maxSum = nums[i] > maxSum ? nums[i] : maxSum;
} else {
maxSum = sum > maxSum ? sum : maxSum;
}
pre.push_back(maxSum);
}
}
int maxPostSubArrays(vector<int> &nums, vector<int> &post) {
int maxSum = nums[nums.size() - 1];
int sum = 0;
for (int i = nums.size() - 1; i > 0; i--) {
sum += nums[i];
if (sum < 0) {
sum = 0;
maxSum = nums[i] > maxSum ? nums[i] : maxSum;
} else {
maxSum = sum > maxSum ? sum : maxSum;
}
post.push_back(maxSum);
}
}
