algoadvance

1. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The array contains only one element.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum = 23.

Clarifying Questions

1. Q: Can the input array be empty? A: No, the input array will contain at least one element.
2. Q: Can the input array contain only negative numbers? A: Yes, the input array can contain all negative numbers.
3. Q: What is the maximum length of the input array? A: Typically up to 10^5 for most competitive programming problems, but we should assume it can be quite large.

Strategy

To solve this problem efficiently, we’ll use Kadane’s Algorithm. This is a classic dynamic programming approach with the following steps:

1. Initialize two variables: current_subarray to keep track of the current subarray sum and max_subarray to store the maximum sum found so far.
2. Iterate through the array elements:
   • Update current_subarray to be the maximum of the current element itself or the sum of current_subarray and the current element.
   • Update max_subarray to be the maximum of max_subarray and current_subarray.
3. Return max_subarray as the result.

Code

Here’s how you can implement this in Python:

def maxSubArray(nums):
    # Initialize the current subarray sum to the first element
    current_subarray = nums[0]
    # Initialize the maximum subarray sum to the first element
    max_subarray = nums[0]
    
    # Start iterating from the second element
    for num in nums[1:]:
        # Update current subarray sum: do we create a new subarray starting from current element
        # or do we continue with the existing subarray
        current_subarray = max(num, current_subarray + num)
        # Update the maximum subarray sum found so far
        max_subarray = max(max_subarray, current_subarray)
    
    return max_subarray

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the array. This is because we only pass through the array once.
• Space Complexity: O(1), as we are using a constant amount of extra space.

This approach ensures that the solution is efficient and works well even for large inputs.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?