1. 暴力枚举
2. “聪明”枚举
3. 分治法
分：两个基本等长的子数组，分别求解T(n/2)
合：跨中心点的最大子数组合（枚举）O(n)
时间复杂度：O(n*logn)
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
int size = nums.size();
if (size == ) {
return nums[];
}
int *data = nums.data();
return helper(data, size);
}
int helper(int *data, int n) {
if ( n == ) {
return data[];
}
int mid = n >> ;
int ans = max(helper(data, mid), helper(data + mid, n - mid));
int now = data[mid - ], may = now;
for (int i = mid - ; i >= ; i--) {
may = max(may, now += data[i]);
}
now = may;
for (int i = mid; i < n; i++) {
may = max(may, now += data[i]);
}
return max(ans, may);
}
};
4. dp（不枚举子数组，枚举方案）
dp[i]表示以a[i]结尾的最大子数组的和
dp[i] = max(dp[i-1]+a[i], a[i])
包含a[i-1]:dp[i-1]+a[i]
不包含a[i-1]:a[i]
初值：dp[0] = a[0]
答案：最大的dp[0...n-1]
时间：O(n)
空间：O(n)
空间优化：dp[i]要存吗？
endHere = max(endHere+a[i], a[i])
answer = max(endHere, answer)
优化后的空间：O(1)
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
int size = nums.size();
if (size == ) {
return nums[];
}
vector<int> dp(size);
dp[] = nums[];
int ans = dp[];
for (int i=; i<size; i++) {
dp[i] = max(dp[i - ] + nums[i], nums[i]);
ans = max(ans, dp[i]);
}
return ans;
}
};
空间优化
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
int size = nums.size();
if (size == ) {
return nums[];
}
int endHere = nums[];
int ans = nums[];
for (int i=; i<size; i++) {
endHere = max(endHere + nums[i], nums[i]);
ans = max(ans, endHere);
}
return ans;
}
};
5. 另外一种线性枚举
定义：sum[i] = a[0] + a[1] + a[2] + ... + a[i] i>=0
sum[-1] = 0
则对0<=i<=j：
a[i] + a[i+1] + ... + a[j] = sum[j] - sum[i-1]
我们就是要求这样一个最大值：
对j我们可以求得当前的sum[j],取的i-1一定是之前最小的sum值，用一个变量记录sum的最小值
时间：O(n)
空间：O(1)
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
int size = nums.size();
if (size == ) {
return nums[];
}
int sum = nums[];
int minSum = min(, sum);
int ans = nums[];
for (int i = ; i < size; ++i) {
sum += nums[i];
ans = max(ans, sum - minSum);
minSum = min(minSum, sum);
}
return ans;
}
};