# LeetCode Easy 53. Maximum Subarray

tags: leetcode

30-Day LeetCoding Challengeが始まったので問題を解いていきます

問題

• Problems

アイデア

整数列が与えられるので，その部分数列の和が最大と成る配列を探せという問題です．

解法

Kadane's Algorithm

• 配列の全ての要素を走査します．
• 今までの最大値max_so_far，現在続いている数列の和の最大値cur_max_sumとします．
  • 現在の値の方が今までの最大値よりも大きい場合は最大値を更新します．
  • 現在の値が負の場合は0とします

計算量

配列の数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_so_far = -float('inf')
        cur_max_sum = 0
        for i in range(len(nums)):
            cur_max_sum += nums[i]
            if max_so_far < cur_max_sum:
                max_so_far = cur_max_sum
            
            if cur_max_sum < 0:
                cur_max_sum = 0
        
        return max_so_far

こうも書けるらしいです．

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i - 1])            
        return max(nums)