连续数组求最长子段和

本文主要是介绍连续数组求最长子段和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

来源：力扣（LeetCode）
链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

数组，连续最大子段和,

3、思路

dp，一趟遍历，更新dp数组，当前dp[i]的来路，要么是dp[i-1]+数组当前值，要么直接是nums的当前值，判断依据是：dp[i-1]是正是负！然后最后的结果是dp数组中的最大值，而不是dp数组的最后一个元素

dp[i]=max(dp[i-1]+nums[i],nums[i])
res=max(res,dp[i]);

4、notes

这个是看dp[i-1]的正负，考虑dp[i-1]+nums[i],还是直接nums[i]

之前一个题：求两个字符串的最长公共子串，如果相等就dp[i][j]=dp[i-1][j-1]+1; 如果不等就直接把dp[i][j]赋值为0，

5、复杂度

时间：一次遍历O(N)
空间：dp数组O(N)
如果是直接原数组上更改就是O(1);

6、code

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int>dp(n,0);int res=nums[0];dp[0]=nums[0];for(int i=1;i<n;i++){dp[i]=dp[i-1]>0 ?dp[i-1]+nums[i]:nums[i];res=max(res,dp[i]);}return res;}
};

直接在原数组中改

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();int res=nums[0];for(int i=1;i<n;i++){nums[i]=nums[i-1]>0 ?nums[i-1]+nums[i]:nums[i];res=max(res,nums[i]);}return res;}
};

这篇关于连续数组求最长子段和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---