LeetCode—Divide and Conquer--53. Maximum Subarray

本文主要是介绍LeetCode—Divide and Conquer--53. Maximum Subarray，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：https://leetcode.com/problems/maximum-subarray/?tab=Description
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
求最大的连续子串和。
分析：动态规划问题(DP)。要找最大子串的和，需要遍历数组，不断保存更大的和值，同时在和值小于0的时候舍弃和的值。
C++代码：

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

这篇关于LeetCode—Divide and Conquer--53. Maximum Subarray的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---