|
| 1 | +# 53. Maximum Subarray |
| 2 | +LeetCode problem: [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) |
| 3 | + |
| 4 | +## Problem |
| 5 | +> Given an integer array nums, find the subarray with the largest sum, and return its sum. |
| 6 | +
|
| 7 | +``` |
| 8 | +Example 1: |
| 9 | +Input: nums = [-2,1,-3,4,-1,2,1,-5,4] |
| 10 | +Output: 6 |
| 11 | +Explanation: The subarray [4,-1,2,1] has the largest sum 6. |
| 12 | +``` |
| 13 | + |
| 14 | +## Thoughts |
| 15 | +* Imagine the size of nums is `i`, let us consider if the same question is applied to the `subarray` of `nums` from index `0` to `i - 1`. |
| 16 | +* The answer is `yes`. Then let us think if the `i - 1`'s answer could impact the answer of `i`. |
| 17 | +* The answer is still `yes`. What would be the impact? |
| 18 | +* For index `i`, |
| 19 | +if the `previous sum` is negative, we can discard it; |
| 20 | +if the `previous sum` is positive, we can add it to the `current sum`. |
| 21 | +* So we can use dynamic programming to solve the problem, but we should use the `current sum` instead of the `largest sum` in the `dp` array because `largest sum` is recorded in the `dp` array. |
| 22 | + |
| 23 | +### Steps of dynamic programming |
| 24 | +These five steps are a pattern for solving dynamic programming problems. |
| 25 | + |
| 26 | +1. Define the `dp` array |
| 27 | + * `dp[i]` represents the `current sum` at index `i`. |
| 28 | +2. Determine the `dp` array's recurrence formula |
| 29 | + * `dp[i] = max(nums[i], dp[i - 1] + nums[i])`. |
| 30 | +3. Determine the `dp` array's initial value |
| 31 | + * `dp[i] = nums[i]` would be good. |
| 32 | +4. Determine the `dp` array's traversal order |
| 33 | + * `dp[i]` depends on `dp[i - 1]`, so we should traverse the `dp` array from left to right. |
| 34 | +5. Check the `dp` array's value |
| 35 | + * Print the `dp` to see if it is as expected. |
| 36 | + |
| 37 | +### Complexity |
| 38 | +* Time: `O(n)`. |
| 39 | +* Space: `O(n)`. |
| 40 | + |
| 41 | +## Python |
| 42 | +```python |
| 43 | +class Solution: |
| 44 | + def maxSubArray(self, nums: List[int]) -> int: |
| 45 | + dp = nums.copy() |
| 46 | + |
| 47 | + for i in range(1, len(dp)): |
| 48 | + dp[i] = max(nums[i], dp[i - 1] + nums[i]) |
| 49 | + |
| 50 | + return max(dp) |
| 51 | +``` |
| 52 | + |
| 53 | +## JavaScript |
| 54 | +```javascript |
| 55 | +var maxSubArray = function(nums) { |
| 56 | + let dp = [...nums] |
| 57 | + |
| 58 | + for (let i = 1; i < dp.length; i++) { |
| 59 | + dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]) |
| 60 | + } |
| 61 | + |
| 62 | + return Math.max(...dp) |
| 63 | +}; |
| 64 | +``` |
0 commit comments