文章目录
-
-
-
- 最大子序和问题
-
- 基础解法
- 利用特性
- 动态规划
- 分治
-
-
最大子序和问题
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
基础解法
将容器所有的可能组合都进行求值得出其中最大值。
int maxSubArray(vector<int>& nums) {
int size = nums.size();
int value = 0;
int result = nums[0]; // 将第一个值最为初始比较值
for (int start = 0; start < size; start++)
{
value = 0;
for(int j = start; j < size; j++)
{
value += nums[j];
if(result < value)
{
result = value;
}
}
}
return result;
}
-
时间复杂度
O(n^2)
-
空间复杂度
O(1)
利用特性
对于该问题,则必有最大得组合开始和结尾得数据均为正数 ,不可能存在开始或结束值为负数求得最大值。
int maxSubArray(vector<int>& nums) {
int res = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0)
sum += num;
else // 值为负数,重新开始累计
sum = num;
res = std::max(res, sum); // 求得最大值
}
return res;
}
-
时间复杂度
O(n)
-
空间复杂度
O(1)
动态规划
实际上是把特性,提取出来理论。
假设数组nums的长度为N,则下标范围为[0,N-1]
我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」,那么很显然我们要求的答案就是:
所有f(i)中最大的那一个。
因此我们只需要求出每个位置的 f(i),然后返回 f 数组中的最大值即可。那么我们如何求 ff(i) 呢?我们可以考虑nums[i]单独成为一段还是加入 f(i-1) 对应的那一段,这取决nums[i] 和 f(i-1) +nums[i] 的大小,我们希望获得一个比较大的,于是可以写出如下的动态转移方程,求得nums[i],与f(i-1)+nums[i]中大的那个。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x); // 求得f(i-1)+nums[i] 与num[i]中最大的值 (公式2)
maxAns = max(maxAns, pre); // 求得记录之前的值与上面的值中最大的值。 (公式1)
}
return maxAns;
}
};
-
时间复杂度
O(n)
-
空间复杂度
O(1)
分治
分治思想就是将一个问题分解成为N个子问题,然后将多个解合并为一。