53. 最大子序和（Maximum Subarray）

• 題解
• • 動态規劃
  • • 複雜度分析
    • Python
    • Java(待完成)

題解

動态規劃

1. 定義目前最大連續子序列和 c u r _ s u m = 0 cur\_sum=0 cur_sum=0，最大子序和 r e s = n u m s [ 0 ] res=nums[0] res=nums[0]，數組長度 n n n
2. 對數組進行周遊，對于 n u m s [ i ] nums[i] nums[i]，存在兩種情況：
   • 若目前最大連續子序列和 c u r _ s u m > 0 cur\_sum>0 cur_sum>0，說明 c u r _ s u m cur\_sum cur_sum對後續結果有着正向增益，即能使後續結果繼續增大，則繼續加和 c u r _ s u m = c u r _ s u m + n u m [ i ] cur\_sum=cur\_sum+num[i] cur_sum=cur_sum+num[i]。
   • 若目前最大連續子序列和 c u r _ s u m < = 0 cur\_sum<=0 cur_sum<=0，說明 c u r _ s u m cur\_sum cur_sum對後續結果沒有增益或負向增益，即若存在更大的加和，一定是從下一進制素開始，加上 c u r _ s u m cur\_sum cur_sum，隻會使結果更小。是以，令 c u r _ s u m cur\_sum cur_sum更新為 n u m s [ i ] nums[i] nums[i]。
   • 更新最大子序和 r e s res res, r e s = m a x ( r e s , c u r s u m ) res=max(res,cur_sum) res=max(res,curs​um),始終保留最大結果。

複雜度分析

• 時間複雜度： O ( n ) O\left(n\right) O(n)
• 空間複雜度： O ( 1 ) O(1) O(1)

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_sum=0
        res=nums[0]
        n=len(nums)
        for i in range(n):
            if(cur_sum>0):
                cur_sum+=nums[i]
            else:
                cur_sum=nums[i]
            res=max(res,cur_sum)    
        return res
           

Java(待完成)