本文主要是介绍leetcode Maximum Subarray 最大子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Maximum Subarray
Total Accepted: 28381 Total Submissions: 83696 My Submissions
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.
设数组为A[n], dp[n-1]是前n-1个数的最大子序列,那么dp[n]=dp[n-1]>0?dp[n-1]+A[n]:A[n].用这个算法从最左边到最右边扫描连续子序列的和.
那么最大的子序列怎么求。每次都用之求maxSum=max{dp[n],maxSum}保存最大的子序列。
对于元素n=0, sum=A[0],最大序列和为maxSum=A[0] 显然成立,
根据循环不变性.对于n
1、设dp[n-1]当前某段连续子序列的和,我们假设为A[n-1]=dp[n-1]，即假设A[n-1]为该段前面的子序列和.如果A[n-1]>=0,那么A[n-1]+A[n]自然是{A[n-1],A[n]}这个序列的最大值。意味着这段连续子序列仍然增加，并把A[n]包含进这段连续子序列,这段连续子序列的值相应也增加了.
2、如果A[n-1]<0,那么A[n]就是这个连续子序列的最大值。意味重新开始了一段新的连续子序列。
3、假设maxSum为之前的最大连续子序列和,使用maxSum=max(A[n],maxSum)可以求前一段连续子序列和当前子序列的最大值，这个函数保证了在n时,maxSum仍然是A[0].....A[n]的最大连续子序列和.
在n结束时仍然满足循环不变性，算法证毕.
class Solution {
public:int maxSubArray(int A[], int n) {int sum=A[0],maxSum=A[0];for(int i=1;i<n;i++){if(sum<0) sum=0;sum+=A[i];maxSum=max(sum,maxSum);}return maxSum;}
};这篇关于leetcode Maximum Subarray 最大子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
