'''
53. Maximum Subarray


Given an integer array nums, find the 
subarray
with the largest sum, and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.


'''


class Solution:
    def maxSubArray(self, nums:list):
        #check if there is only one value, then just return it
        #as that would be the max
        if len(nums) == 1:
            return nums[0]

        #initialize the vals as 0
        maxSum = 0
        currMax = 0

        for x in range(len(nums)):
            #add the currMax to the current value in the list
            currMax+= nums[x]
            #if the currMax is less than 0 then reset back to 0
            if currMax < 0:
                currMax = 0
            #get the max by comparing both the maxSum and the currentMax
            maxSum = max(maxSum,currMax)

        #return the max contigeous val
        return maxSum



if __name__ == '__main__':
    
    nums = [-2,1,-3,4,-1,2,1,-5,4] #should return 6
    obj1 = Solution()

    print(obj1.maxSubArray(nums))