Maximum Subarray Solution for Capgemini

Company: Capgemini · Difficulty: Hard · Topics: Array, Dynamic Programming, Divide and Conquer

Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous part of an array.

Examples

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

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

Example 4:

Input: nums = [-1,-2,-3,-4]

Output: -1

Explanation: The subarray [-1] has the largest sum -1.

Intuition

The key insight is that we can solve this problem using Kadane's algorithm, which keeps track of the maximum sum ending at each position. If the current sum becomes negative, we reset it to the current element.

Approach

Approach 1: Kadane's Algorithm (Optimal)

1. Initialize maxSum and currentSum to the first element

2. For each element starting from the second:

Update currentSum = max(currentSum + current_element, current_element)
Update maxSum = max(maxSum, currentSum)

3. Return maxSum

Approach 2: Dynamic Programming

1. Create a DP array where dp[i] represents max sum ending at index i

2. dp[i] = max(nums[i], dp[i-1] + nums[i])

3. Find maximum value in DP array

Approach 3: Brute Force

1. Check all possible subarrays

2. Calculate sum for each subarray

3. Keep track of maximum sum found

Dry Run

Let's trace through Example 1: nums = [-2,1,-3,4,-1,2,1,-5,4]

Kadane's Algorithm:

i=0: currentSum = -2, maxSum = -2
i=1: currentSum = max(-2+1, 1) = 1, maxSum = max(-2, 1) = 1
i=2: currentSum = max(1+(-3), -3) = -2, maxSum = max(1, -2) = 1
i=3: currentSum = max(-2+4, 4) = 4, maxSum = max(1, 4) = 4
i=4: currentSum = max(4+(-1), -1) = 3, maxSum = max(4, 3) = 4
i=5: currentSum = max(3+2, 2) = 5, maxSum = max(4, 5) = 5
i=6: currentSum = max(5+1, 1) = 6, maxSum = max(5, 6) = 6
i=7: currentSum = max(6+(-5), -5) = 1, maxSum = max(6, 1) = 6
i=8: currentSum = max(1+4, 4) = 5, maxSum = max(6, 5) = 6

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Kadane's Algorithm (Optimal)

Time Complexity: O(n) - We traverse the array once

Space Complexity: O(1) - Only need a few variables

Solution 2: Dynamic Programming

Time Complexity: O(n) - We traverse the array once

Space Complexity: O(n) - Need DP array

Solution 3: Brute Force

Time Complexity: O(n²) - We check all subarrays

Space Complexity: O(1) - Only need a few variables