【一刷《剑指Offer》】面试题 31：连续子数组的最大和

本文主要是介绍【一刷《剑指Offer》】面试题 31：连续子数组的最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客对应题目链接：连续子数组最大和_牛客题霸_牛客网 (nowcoder.com)

力扣对应题目链接：53. 最大子数组和 - 力扣（LeetCode）

核心考点 ：简单动归问题。

---

一、《剑指Offer》对应内容

---

二、分析题目

1、贪心

从前往后迭代，一个个数字加过去，如果 sum<res，则重新开始找子序串。

---

2、动态规划

• 定义状态 dp[i]：表示以 i 下标结尾的最大连续子序列的和。
• 状态递推：dp[i] = max(dp[i-1]+array[i], array[i]) 【 注意：这里一定要连续关键字】
• 状态的初始化：dp[0] = array[0], max = array[0]

很明显，上面的这个做法只会使用到 dp[i] 和 dp[i-1]，所以是有优化的可能的。

---

三、代码

//牛客
#include <iostream>
using namespace std;const int N=2e5+10;
int arr[N], dp[N];int main()
{int n;cin >> n;for(int i=0; i<n; i++) cin >> arr[i];dp[0]=arr[0];int res=arr[0];for(int i=1; i<n; i++){dp[i]=max(dp[i-1]+arr[i], arr[i]);res=max(res, dp[i]);}cout << res << endl;return 0;
}//基于上面代码的优化
#include <iostream>
using namespace std;const int N=2e5+10;
int arr[N];int main()
{int n;cin >> n;for(int i=0; i<n; i++) cin >> arr[i];int sum=arr[0];int res=arr[0];for(int i=1; i<n; i++){if(sum>=0) sum+=arr[i];else sum=arr[i];res=max(res, sum);}cout << res << endl;return 0;
}

//力扣
//方法一
class Solution {
public:int maxSubArray(vector<int>& nums) {int res=-2e4;int sum=0;for(int i=0; i<nums.size(); i++){sum+=nums[i];if(sum>res)res=sum;if(sum<0)sum=0;}return res;}
};//方法二(与上面牛客的写法不太一样)
class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int> dp(n+1);int res=-2e4;for(int i=1; i<=n; i++){dp[i]=max(nums[i-1], dp[i-1]+nums[i-1]);if(dp[i]>res) res=dp[i];}return res;}
};

这篇关于【一刷《剑指Offer》】面试题 31：连续子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---