maximum_subarray

View Source

 1# @leet start
 2class Solution:
 3    def maxSubArray(self, nums: list[int]) -> int:
 4        """
 5        To find the maximum subarray, we start off by counting the first
 6        number as the current and max.
 7
 8        Then for all the other numbers, we only want to keep it if we added it to
 9        our current total and keep it only if the total is non-negative.
10        We use `curr = max(curr, num + curr)` to do that for us.
11        Finally, we update the max every iteration with the curr.
12
13        At the end, we return the max we've seen so far.
14        """
15        curr, max_so_far = nums[0], nums[0]
16
17        for num in nums[1:]:
18            curr = max(curr, num + curr)
19            max_so_far = max(max_so_far, curr)
20
21        return max_so_far
22
23
24# @leet end
25
26
27def test():
28    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def maxSubArray(self, nums: list[int]) -> int:
 5        """
 6        To find the maximum subarray, we start off by counting the first
 7        number as the current and max.
 8
 9        Then for all the other numbers, we only want to keep it if we added it to
10        our current total and keep it only if the total is non-negative.
11        We use `curr = max(curr, num + curr)` to do that for us.
12        Finally, we update the max every iteration with the curr.
13
14        At the end, we return the max we've seen so far.
15        """
16        curr, max_so_far = nums[0], nums[0]
17
18        for num in nums[1:]:
19            curr = max(curr, num + curr)
20            max_so_far = max(max_so_far, curr)
21
22        return max_so_far

def maxSubArray(self, nums: list[int]) -> int: View Source

 4    def maxSubArray(self, nums: list[int]) -> int:
 5        """
 6        To find the maximum subarray, we start off by counting the first
 7        number as the current and max.
 8
 9        Then for all the other numbers, we only want to keep it if we added it to
10        our current total and keep it only if the total is non-negative.
11        We use `curr = max(curr, num + curr)` to do that for us.
12        Finally, we update the max every iteration with the curr.
13
14        At the end, we return the max we've seen so far.
15        """
16        curr, max_so_far = nums[0], nums[0]
17
18        for num in nums[1:]:
19            curr = max(curr, num + curr)
20            max_so_far = max(max_so_far, curr)
21
22        return max_so_far

To find the maximum subarray, we start off by counting the first number as the current and max.

Then for all the other numbers, we only want to keep it if we added it to our current total and keep it only if the total is non-negative. We use curr = max(curr, num + curr) to do that for us. Finally, we update the max every iteration with the curr.

At the end, we return the max we've seen so far.

def test(): View Source

28def test():
29    assert 2 + 2 == 4