本文最后更新于 426 天前，其中的信息可能已经有所发展或是发生改变。
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为6。
示例2：
输入：nums = [1]
输出：1
示例3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
- 1<=nums.length<=10^5
- -10^4<=nums[i]<=10^4
进阶：如果你已经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解
解题思路
- 确定dp数组的含义 dp[i]：包含下标
- 递推公式
i（nums[i]）的最大连续子序列和为dp[i]
- nums[i]加入子序列之和：dp[i] = dp[i-1] + nums[i]
- 从头开始计算子序列之和：dp[i] = nums[i] 取两者的最大值：
dp[i] = max(dp[i-1] + nums[i], nums[i]
- dp数组初始化 dp[0] = nums[0]
- 确定遍历顺序 dp[i]是根据dp[i-1]推导而来，故遍历顺序为从前往后
- 打印dp数组
代码实现
- 核心模式
class Solution{
public:
int maxSubArray(vector<int>& nums){
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
// initialize the Dp array
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++){
dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
// update the maxSubArray
if (dp[i] > result) result = dp[i];
}
return result;
}
};
- ACM模式 "dynamicPro.h"
#include <iostream>
#include "dynamicPro.h"
class Solution{
public:
int maxSubArray(vector<int>& nums){
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
// initialize the Dp array
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++){
dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
// update the maxSubArray
if (dp[i] > result) result = dp[i];
}
printVector(dp);
return result;
}
};
int main(){
vector<int> case1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
vector<int> case2 = {1};
vector<int> case3 = {5, 4, -1, 7, 8};
Solution solution;
cout << "Result1's DP Array = " << solution.maxSubArray(case1) << endl;
cout << "Result2's DP Array = " << solution.maxSubArray(case2) << endl;
cout << "Result3's DP Array = " << solution.maxSubArray(case3) << endl;
return 0;
}
- 输出
Result1's DP Array = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
6
Result2's DP Array = [1]
1
Result3's DP Array = [5, 9, 8, 15, 23]
23
- 补充 贪心解法