#53.?? Maximum Subarray

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.

題解：動態規劃解這題，假設max_sum記錄了前k個元素的最大子序列和，這時添加第k+1個元素，由于是連續子序列這個限制，所以如果k+1這個元素之前的和是小于0的，那么對于增大k+1這個元素從而去組成最大子序列是沒有貢獻的，所以可以把sum 置0。舉個例子，-1， -2 ，4， -5， 7這里假定7為第k+1個元素，那么很明顯可以看出，之前的sum = -5 + 4 =-1，那么這樣對于7來說只會減少它，所以直接置sum = 0， 0 + 7才能得到正確的答案。再拓展這個數組， -1， -2， 4， -5， 7， 1 這里1之前的sum = 7 > 0，對于后面的1來組成最大子序列是有貢獻的，所以sum = 7 + 1 =8。再注意一點，只要sum不減到負數，中間出現小于0的元素是沒關系的，sum仍然可以繼續累加。

即臨時sum[k+1]=max{nums[i],nums[i]+sum[k]},用max_sum存儲最大的子序列和不斷更新即可。

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

?

轉載于:https://www.cnblogs.com/fengxw/p/6083786.html

總結

以上是生活随笔為你收集整理的Leetcode-53 Maximum Subarray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。