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. (Problem)

We can find the max subarray by checking all possible subarrays of the array, in python this can be done quite easily via the slicing operation.

				
	class Solution:
		def maxSubArray(self, nums: List[int]) -> int:
			maxval=nums[0]
			for i in range(len(nums)-2):
				for j in range(i+1,len(nums)-1):
					val = sum(nums[i:j])
					maxval = max(val,maxval)
			return maxval
							
			

However the time complexity of such an approach is very poor O(n³). This is beacuse even the sum() function take O(n) to compute.

A better approach is to always check the current sum of the array.

				
	[-2,1,-3,4,-1,2,1,-5,4]

	initially -2 -> -1 -> -4 ...
							
			

We can notice that -2 did not help us at all, all it did was lower the value, hence whenever we encounter a negative current sum we should set to 0.

We can then just iterate over the array and add the value present in ith position, followed by checking the max(current sum, maximun value found so far).

				
	[-2,-3,-1,-5]
							
			

Suppose we get the above scenario where all the numbers are negative, then we just need to get the highest value. This can be achieved by initially setting the maxval as the first number of the array, after which the current sum will only decrease -> it will set to 0, then it will add the negative value in ith position -> compare itself to maxval and the higher number will be chosen.

				
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            maxval = nums[0]
            curSum=0
            
            for i in range(len(nums)):
                if(curSum<0):
                    curSum=0
                curSum+=nums[i]
                maxval = max(curSum,maxval)
            return maxval
							
			

Time Complexity => o(n)

Space Complexity => o(1)