Maximum Subarray Solution for Accenture

Company: Accenture · Difficulty: Medium · 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.

Key Understanding:

• A subarray is a contiguous sequence of elements from the array
• We need to find the subarray with the maximum sum
• The array can contain negative numbers
• The subarray can be of any length (including single element)
• We only need to return the sum, not the subarray itself

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: 4 + (-1) + 2 + 1 = 6
• Other subarrays have smaller sums:
• [-2,1,-3,4] = 0
• [1,-3,4,-1,2,1] = 4
• [2,1,-5,4] = 2

Example 2:

Input: nums = [1]

Output: 1

Explanation:

• The array has only one element, so the maximum subarray is [1]
• 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: 5 + 4 + (-1) + 7 + 8 = 23
• This is the entire array, which gives the maximum sum

Example 4:

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

Output: -1

Explanation:

• All elements are negative
• The maximum subarray is [-1] with sum -1
• Any larger subarray would have a smaller (more negative) sum

Intuition

The key insight is that we can use dynamic programming to keep track of the maximum sum ending at each position. If the current sum becomes negative, we start a new subarray from the current element.

Core Concept:

• At each position, we decide whether to extend the current subarray or start a new one
• If extending the current subarray gives a better result, we extend it
• If starting a new subarray from the current element gives a better result, we start fresh
• We keep track of the global maximum sum seen so far

Why This Works:

• If the current sum becomes negative, it's better to start fresh from the current element
• A negative sum will only decrease the sum of any future subarray that includes it
• By keeping track of the maximum sum ending at each position, we can find the global maximum

Approach

Approach 1: Kadane's Algorithm (Optimal)

Algorithm:

1. Initialize maxSum and currentSum to the first element

2. Iterate from the second element to the end

3. For each element:

• currentSum = max(currentSum + num, num)
• maxSum = max(maxSum, currentSum)

4. Return maxSum

Why This Works:

• At each step, we decide whether to extend the current subarray or start a new one
• currentSum represents the maximum sum ending at the current position
• maxSum keeps track of the global maximum sum seen so far
• If currentSum becomes negative, we start fresh from the current element

Complexity Analysis:

• Time: O(n) - Single pass through the array
• Space: O(1) - Only constant variables needed

Approach 2: Divide and Conquer

Algorithm:

1. Divide the array into two halves

2. Recursively find the maximum subarray in the left half

3. Recursively find the maximum subarray in the right half

4. Find the maximum subarray that crosses the middle

5. Return the maximum of the three values

Why This Works:

• The maximum subarray must be either:
• Entirely in the left half
• Entirely in the right half
• Crossing the middle (part in left, part in right)
• We find all three possibilities and take the maximum

Complexity Analysis:

• Time: O(n log n) - We divide the problem recursively
• Space: O(log n) - Due to recursion stack

Approach 3: Brute Force

Algorithm:

1. Check all possible subarrays

2. Calculate the sum for each subarray

3. Keep track of the maximum sum

Why This Works:

• We check every possible subarray
• Guaranteed to find the correct answer
• Simple but inefficient

Complexity Analysis:

• Time: O(n²) - We check n(n+1)/2 subarrays
• Space: O(1) - Only constant variables needed

Dry Run

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

Kadane's Algorithm:

Initial State: maxSum = -2, currentSum = -2

Step 1: i = 1, num = 1

• currentSum = max(-2 + 1, 1) = max(-1, 1) = 1
• maxSum = max(-2, 1) = 1
• State: maxSum = 1, currentSum = 1

Step 2: i = 2, num = -3

• currentSum = max(1 + (-3), -3) = max(-2, -3) = -2
• maxSum = max(1, -2) = 1
• State: maxSum = 1, currentSum = -2

Step 3: i = 3, num = 4

• currentSum = max(-2 + 4, 4) = max(2, 4) = 4
• maxSum = max(1, 4) = 4
• State: maxSum = 4, currentSum = 4

Step 4: i = 4, num = -1

• currentSum = max(4 + (-1), -1) = max(3, -1) = 3
• maxSum = max(4, 3) = 4
• State: maxSum = 4, currentSum = 3

Step 5: i = 5, num = 2

• currentSum = max(3 + 2, 2) = max(5, 2) = 5
• maxSum = max(4, 5) = 5
• State: maxSum = 5, currentSum = 5

Step 6: i = 6, num = 1

• currentSum = max(5 + 1, 1) = max(6, 1) = 6
• maxSum = max(5, 6) = 6
• State: maxSum = 6, currentSum = 6

Step 7: i = 7, num = -5

• currentSum = max(6 + (-5), -5) = max(1, -5) = 1
• maxSum = max(6, 1) = 6
• State: maxSum = 6, currentSum = 1

Step 8: i = 8, num = 4

• currentSum = max(1 + 4, 4) = max(5, 4) = 5
• maxSum = max(6, 5) = 6
• State: maxSum = 6, currentSum = 5

Final Result: 6

Divide and Conquer Approach:

Array: [-2,1,-3,4,-1,2,1,-5,4]

Divide: Left = [-2,1,-3,4], Right = [-1,2,1,-5,4]

Left Half: [-2,1,-3,4]

• Max in left: 4 (subarray [4])
• Max in right: 1 (subarray [1])
• Max crossing: 2 (subarray [1,-3,4])
• Max of left half: 4

Right Half: [-1,2,1,-5,4]

• Max in left: 2 (subarray [2])
• Max in right: 4 (subarray [4])
• Max crossing: 6 (subarray [2,1,-5,4])
• Max of right half: 6

Crossing Middle: Find max subarray that includes elements from both halves

• Max sum ending at middle: 4 (from left)
• Max sum starting from middle: 6 (from right)
• Total crossing sum: 4 + 6 = 10

Final Result: max(4, 6, 10) = 10

Key Insights

1. Dynamic Programming: Kadane's algorithm is a classic dynamic programming problem

2. Local vs Global Maximum: We maintain both local maximum (currentSum) and global maximum (maxSum)

3. Negative Sums: If current sum becomes negative, it's better to start fresh

4. Contiguous Subarray: The subarray must be contiguous (no gaps)

5. Single Element: A single element can be the maximum subarray

Edge Cases

1. All Negative Numbers: Maximum subarray is the largest single element

2. All Positive Numbers: Maximum subarray is the entire array

3. Single Element: The element itself is the maximum subarray

4. Empty Array: Not possible as per constraints (1 ≤ nums.length ≤ 10^5)

5. Large Numbers: Need to handle integer overflow

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) - We use only constant extra space

Advantages:

• Most efficient solution
• Constant space usage
• Single pass through array
• Handles all edge cases

Disadvantages:

• Requires understanding of dynamic programming
• May not be intuitive at first

Solution 2: Divide and Conquer

Time Complexity: O(n log n) - We divide the problem recursively

Space Complexity: O(log n) - Due to recursion stack

Advantages:

• Demonstrates divide and conquer technique
• Can be extended to find the subarray itself
• Good for understanding recursion

Disadvantages:

• Less efficient than Kadane's algorithm
• More complex implementation
• Uses recursion stack space

Solution 3: Brute Force

Time Complexity: O(n²) - We check n(n+1)/2 subarrays

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Simple and straightforward
• Easy to understand and implement
• Guaranteed to find correct answer

Disadvantages:

• Highly inefficient for large arrays
• Not suitable for production use
• Time complexity grows quadratically

More Accenture coding questions