Maximum Sum of a Contiguous Sub array

Maximum Sum of a Contiguous Subarray

Find the contiguous subarray within an array (containing at least one number) that has the largest sum.

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray [4, -1, 2, 1] has the largest sum =6

Solution: Bottom-Up Dynamic Programming

class Solution:

    def contiguous_subarray(self, nums):
		n = len(nums)
		dp={}
		current_max =0
		running_sum =0
		for i in range(n):

			new_sum = running_sum + nums[i]
			running_sum = new_sum if new_sum > 0 else 0
			if i > 0 and i <=n:
				current_max=max(running_sum, current_max, nums[i], nums[i-1]+nums[i])
				dp[i]=current_max
			else:
				dp[i]=nums[i]
		return dp[n-1]

Let's see what is happening in the code above.

n = len(nums): Get the length of the input list nums.

dp = {}: Initialize an empty dictionary to store the maximum subarray sum at each position.

current_max = 0: Initialize a variable to keep track of the current maximum subarray sum.

running_sum = 0: Initialize a variable to keep track of the running sum of the current subarray.

Iterate through each element in the input list nums:

return dp[n-1]: Return the maximum subarray sum stored at the last index of the dictionary, which corresponds to the maximum sum of the entire array.

The function aims to find the maximum sum of a contiguous subarray using dynamic programming and efficiently updates the running sum and maximum sum at each position.

Time and space Complexity

This solution will not be complete unless I analyze the time and space complexity. Let's explore!

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input list nums. The reason for this is that the algorithm iterates through the input list once, and at each iteration, it performs constant time operations.

Space Complexity

The space complexity is O(n), where n is the length of the input list nums. The primary space usage comes from the dictionary dp, which stores the maximum subarray sum at each position. In the worst case, the size of the dictionary is proportional to the size of the input list.

The remaining variables (n, current_max, running_sum, new_sum) are constant space, which doesn't depend on the input size.

In summary, the solution has a linear time complexity and linear space complexity regarding the input list length.

Here's an alternative more concise code based on the above solution.

class Solution:

    def contiguous_subarray(self, nums):
		n = len(nums)
		dp={}
		dp[0]=nums[0]
		current_max,running_sum =0, 0
		for i in range(1, n):

			new_sum = running_sum + nums[i]
			running_sum = new_sum if new_sum > 0 else 0
			current_max=max(running_sum, current_max, nums[i], nums[i-1]+nums[i])
			dp[i]=current_max
				
		return dp[n-1]

print("bottom-up solution ::",sol.contiguous_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))