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:
new_sum = running_sum + nums[i]: Calculate the new running sum by adding the current element.
running_sum = new_sum if new_sum > 0 else 0: If the new running sum is positive, update it; otherwise, reset it to 0.
if i > 0 and i <= n:: Check if the index i is within bounds.
current_max = max(running_sum, current_max, nums[i], nums[i-1] + nums[i]): Update current_max with the maximum value among the current running sum, the previous maximum, the current element, and the sum of the current and previous elements.
dp[i] = current_max: Store the current maximum subarray sum in the dictionary dp at index i.
else: Handle the case where i is out of bounds.
dp[i] = nums[i]: Store the current element in the dictionary dp at index i.
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]))