最大子数组和(medium)
题目链接:
题目描述:
给你一个整数数组
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
题目解析
解释一下什么是子数组.很简单,我们把数组里面的元素连接一起就可以认为是一个子数组.题目就是求我们子数组的最大和.这里我们用实例3三做演示.
也就是要求的数组里面的最大连续子数组的和.
算法原理
状态表示
按照经验,我们以...为结尾表示状态.
dp[i]:表示以i位置为结尾,我们最大子数组最大的连续和.
状态转移方程
这里我们想一下.对于我们的nums[i].这里我们可以有两个选择.
- 选择nums[i]这一个元素作为我们的子数组 dp[i] = nums[i]
- 和i-1联合作为子数组. dp[i] = dp[i-1]+nums[i]
那么这里我们求最大值.dp[i] = max(nums[i], dp[i-1]+nums[i]);
初始化
借助了i-1位置,那么此时我们多加上一个节点.那么求第一个元素,我们dp[1]一定是第一个元素,那么dp[0] = 0就可以满足这个了.
填表顺序
从左向由填.
返回值
题目要求的最大和,那么我们这里使用一个变量保存最大就可以了.
编写代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return -1;
int n = nums.size();
vector<int> dp(n+1, 0);
int result = INT_MIN;
for(int i = 1; i <= n; i++)
{
dp[i] = max(dp[i-1] + nums[i-1], nums[i-1]);
result = max(result, dp[i]);
}
return result;
}
};