问题描述:
给你一个一维数组,数组值可正可负,要求得到连续子数组的最大和值,子数组的元素至少为1个。
解决方法:
暴力求解法:
通过两层for循环遍历每一种可能的组合,再通过比较得到最大的值。方法实现较为简单,但时间复杂度较高,需要O(n*n),代码如下:
class Solution {
public:
int maxSubArray(vector<int> & nums) {
int number = nums.size();
int currentSum = ;
int max = nums[];
//n个数则总共执行n次循环
for (int i = ; i < number; ++i) {
currentSum = ;
for (int j = i; j < number; ++j) {
currentSum += nums[j];
if (currentSum > max)
max = currentSum;
}
}
return max;
}
};
分治法:
寻找数组的中间值,将原数组划分为左右两个部分,则最大子数组出现的可能情况有三种:
1. 在左边的子数组中
2. 在右边的子数组中
3. 最大子数组跨越左右两个子数组,则中间值middle一定包含在最大子数组中
实现代码如下:
class Solution {
public:
int maxSubArray(vector<int> & nums) {
return findMaxSubArray(nums, , nums.size() - );
}
int findMaxSubArray(vector<int> & nums, int left, int right) {
//当只有一个值时返回该值
if (left == right)
return nums[left];
int mid = (left + right) / ;
//左数组
int leftMax = findMaxSubArray(nums, left, mid);
//右数组
int rightMax = findMaxSubArray(nums, mid + , right);
//包含middle值的数组
int centerMax = findCrossMaxArray(nums, mid, left, right);
//返回三者中的最大者
return findMax(leftMax, rightMax, centerMax);
}
int findCrossMaxArray(vector<int> & nums, int mid, int left, int right) {
int leftSum = , rightSum = ;
int leftMax = nums[mid], rightMax = nums[mid + ];
int i = mid, j = mid + ;
int max = ;
//左半边最大的值
for (; i >= left; --i) {
leftSum += nums[i];
if (leftSum > leftMax)
leftMax = leftSum;
}
//右半边最大的值
for (; j <= right; ++j) {
rightSum += nums[j];
if (rightSum > rightMax)
rightMax = rightSum;
}
max = leftMax + rightMax;
return max;
}
int findMax(int a, int b, int c) {
int temp = ;
if (a > b)
temp = a;
else
temp = b;
if (temp < c)
temp = c;
return temp;
}
};
这个算法的时间复杂度较暴力求解有了一定的提升。设数组的长度为n, 时间复杂度为T(n),则时间复杂度为T(n) = 2 * T(n / 2) + 0(n),可计算得时间复杂度为0(nlgn)。
线性时间算法
代码如下:
class Solution {
public:
int maxSubArray(vector<int> & nums) {
int currentSum = ;
int max = nums[];
for (int i = ; i < nums.size(); ++i) {
currentSum += nums[i];
if (currentSum > max)
max = currentSum;
if (currentSum < )
currentSum = ;
}
return max;
}
};
从第一个数开始累加,如果是正的则一直保持,负的则舍弃重新累加。max一直保留目前的最大值。
动态规划
该算法的思想是已知原数组后面部分的最大子数组nAll以及该部分最前一个元素开始的最大子数组nStart。然后再往前添加一个元素,则此时新数组的最大子数组要么是包含新元素,要么是原来的最大子数组。如果包含新元素,则是新元素本身或者是新元素加上原来的nStart的和。时间复杂度为O(n)。 代码如下:
class Solution {
public:
int maxSubArray(vector<int> & nums) {
int nStart = nums[nums.size() - ];
int nAll = nums[nums.size() - ];
for (int i = nums.size() - ; i >= ; --i) {
nStart = max(nums[i], nums[i] + nStart);
nAll = max(nAll, nStart);
}
return nAll;
}
int max(int x, int y) {
return (x > y) ? x : y;
}
};
问题应用:
如果有一张近期股票的走势图,要问你哪天买入哪天卖出能得到最大收益。此时可以转为最大子数组问题。数组元素为前后两天的股票差值。