MaximumSubarray.py

# Source : https://leetcode.com/problems/maximum-subarray
# Author : Hamza Mogni
# Date   : 2022-01-20

#####################################################################################################
#
# Given an integer array nums, find the contiguous subarray (containing at least one number) which
# has the largest sum and return its sum.
#
# A subarray is a contiguous part of an array.
#
# Example 1:
#
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: [4,-1,2,1] has the largest sum = 6.
#
# Example 2:
#
# Input: nums = [1]
# Output: 1
#
# Example 3:
#
# Input: nums = [5,4,-1,7,8]
# Output: 23
#
# Constraints:
#
# 	1 <= nums.length <= 10^5
# 	-10^4 <= nums[i] <= 10^4
#
# Follow up: If you have figured out the O(n) solution, try coding another solution using the divide
# and conquer approach, which is more subtle.
#####################################################################################################

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maximum = nums[0]

        current = 0

        for nbr in nums:
            if current < 0:
                current = 0

            current += nbr

            maximum = max(maximum, current)

        return maximum


s = Solution()
print(s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))