How to Solve Maximum Subarray
Maximum Subarray Introduction
Maximum Subarray Introduction
The Maximum Subarray problem asks us to find the subarray with the largest sum of a given array. This problem can be solved using dynamic programming and more specifically Kadane's Algorithm.
Maximum Subarray Problem
Maximum Subarray Problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example Inputs and Outputs
Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Example 2
Input: nums = [1]
Output: 1
Example 3
Input: nums = [5, 4, -1, 7, 8]
Output: 23
Maximum Subarray Solutions
Maximum Subarray Solutions
To solve this problem, we can use a technique called Kadane's algorithm. Here's how it works:
Imagine you're walking through the given array from left to right, keeping track of the sum of the subarray you've encountered so far. At each step, you have two options: you can either extend the current subarray by including the current element, or you can start a new subarray from the current element. The idea is to choose the option that gives you the maximum sum.
To do this, you maintain two variables: one to track the current sum and another to store the maximum sum found so far. As you move forward in the array, you update the current sum by adding the current element or starting afresh. Whenever the current sum becomes larger than the maximum sum, you update the maximum sum. By the end of the traversal, the maximum sum will represent the sum of the subarray with the largest sum.
This approach handles different cases like arrays with negative numbers or arrays with only one element. It considers both individual elements and subarrays to find the subarray with the largest sum. The key idea is to dynamically update the current sum and compare it with the maximum sum as you progress through the array. By doing this, we can efficiently find the solution in a single pass through the array.
def maxSubArray(nums):
maxSum = nums[0] # Initialize maxSum with the first element of the array
currentSum = nums[0] # Initialize currentSum with the first element of the array
for i in range(1, len(nums)):
currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)
return maxSum
# Test case 1
nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result1 = maxSubArray(nums1)
print("Maximum subarray sum for nums1:", result1) # Expected output: 6
# Test case 2
nums2 = [1]
result2 = maxSubArray(nums2)
print("Maximum subarray sum for nums2:", result2) # Expected output: 1
# Test case 3
nums3 = [5, 4, -1, 7, 8]
result3 = maxSubArray(nums3)
print("Maximum subarray sum for nums3:", result3) # Expected output: 231def maxSubArray(nums):
2 maxSum = nums[0] # Initialize maxSum with the first element of the array
3 currentSum = nums[0] # Initialize currentSum with the first element of the array
4
5 for i in range(1, len(nums)):
6 currentSum = max(nums[i], currentSum + nums[i])
7 maxSum = max(maxSum, currentSum)
8
9 return maxSum
10
11# Test case 1
12nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
13result1 = maxSubArray(nums1)
14print("Maximum subarray sum for nums1:", result1) # Expected output: 6
15
16# Test case 2
17nums2 = [1]
18result2 = maxSubArray(nums2)
19print("Maximum subarray sum for nums2:", result2) # Expected output: 1
20
21# Test case 3
22nums3 = [5, 4, -1, 7, 8]
23result3 = maxSubArray(nums3)
24print("Maximum subarray sum for nums3:", result3) # Expected output: 23Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of the input array nums. This is because we iterate through each element of the array once.
- Space Complexity: O(1), as we use a constant amount of extra space to store the current sum and maximum sum.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
