深处的记忆——最大子数组和

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

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组

是数组中的一个连续部分。

示例 1：

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

题目意思很简单，最暴力的两层遍历能出结果，但肯定会超时。

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

如何不超时呢，题目要求我们是不需要给出子序列的，只需要最大值即可。那么其实就到了动态规划擅长的地方了，也不需要怕动态规划，这个题还是很简单，各位读者往下看。

        很简单的道理：和负数相加总和会变小，和正数相加总和会变大

 代码：

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

简洁版本： 

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

这篇关于深处的记忆——最大子数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---