Leetcode # 53. Maximum Subarray (Kadane’s Algorithm)

2021.12.09
★★ Medium Dynamic Programming Kadane’s Algorithm LeetCode

https://leetcode.com/problems/maximum-subarray/

Solution

\begin{align}
&\text{max_ending_here } := \mathop{\max}_{i \in [0, j]}\quad{\mathop{\sum}_{k=i}^j{nums[k]}} \\
&\text{max_so_far } := \mathop{\max}_{x, y \in [0, j], x \leq y}\quad{\mathop{\sum}_{k=x}^y{nums[k]}}
\end{align}

Ref: Wikipedia

Python 版

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    max_ending_here = max_so_far = nums[0]
    for num in nums[1:]:
      max_ending_here = max(num, max_ending_here + num)
      max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

C++ 版

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