aboutsummaryrefslogtreecommitdiff
path: root/maximum_subarray.py
blob: 1edbefcd629cbef5c1cf0f152a4fc9604f02007c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 53. Maximum Subarray

"""
given an integer array 'nums', find the subarray with the largest sum, and
return its sum.
"""


class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_sum, curr_sum = float("-inf"), 0
        for i in nums:
            curr_sum += i
            if max_sum < curr_sum:
                max_sum = curr_sum
            if curr_sum < 0:
                curr_sum = 0
        return max_sum


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print(obj.maxSubArray(nums=[1]))
    print(obj.maxSubArray(nums=[5, 4, -1, 7, 8]))