Problem

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

Examples

Example 1:

1
2
3

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

Follow up

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

There are multiple solutions possible to this problem:

  • Brute force - O(n^3)
  • Kadane’s algorithm - O(n)
  • Dynamic Programming - O(n), Space complexity - O(n)
  • Divide and Conquer

Video explanation

Here is the video explaining different methods including naive, divide and conquer and Kadane’s algorithm in detail. Please check it out:

Method 1 - Brute Force

The naive approach involves computing the sum of every possible subarray in the array and keeping track of the maximum sum encountered. This approach uses three nested loops:

  1. Outer Loop: Iterate over each starting point of the subarray.
  2. Middle Loop: Iterate over each ending point of the subarray, starting from the current starting point.
  3. Inner Loop: Calculate the sum of the subarray defined by the outer and middle loop boundaries.

Pseudocode

1
2
3
4
5
6
7
8

max_sum = -infinity
for i from 0 to n-1:
    for j from i to n-1:
        current_sum = 0
        for k from i to j:
            current_sum += nums[k]
        max_sum = max(max_sum, current_sum)
return max_sum

Complexity

  • ⏰ Time complexity: O(n^3) because of the three nested loops.
  • 🧺 Space complexity: O(1) since no additional space is used outside of a few variables.

Method 2 - Optimize on innermost loop

If we look at the previous solution, we don’t need innermost loop that recalculates the sum for each subarray from scratch. Instead, we build on the sum of previous subarrays, achieving a time complexity of O(n^2).

Pseudocode

1
2
3
4
5
6
7

max_sum = -infinity
for i from 0 to n-1:
    current_sum = 0
    for j from i to n-1:
        current_sum += nums[j]
        max_sum = max(max_sum, current_sum)
return max_sum

Complexity

  • ⏰ Time complexity: O(n^2) because of the two nested loops.
  • 🧺 Space complexity: O(1) as we use a constant amount of extra space.

Method 3 - Kadane’s Algorithm 🏆

Kadane’s Algorithm for Maximum Subarray Sum

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 4 - Using Bottom-up DP

We can use Dynamic programming (DP) to solve this problem. The approach involves finding the maximum subarray sum ending at each index and using these results to construct the solution for the subsequent indices.

Algorithm

  1. Subproblems: Define dp[i] to be the maximum subarray sum ending at index i in the array. The
  2. Recurrence relation: dp[i] = max(dp[i-1] + arr[i], arr[i])
    • This means that the maximum sum subarray ending at i is either:
      • The maximum sum subarray ending at i-1 plus the element at i
      • The element at i itself (in case the maximum subarray sum ending at i-1 is negative)
  3. Base case: Generally, the DP solution starts with a base case. In this problem, the base case is: dp[0] = arr[0]
  4. Iterate and Fill the Table: Now fill the table from i = 1 to n
  5. Reconstruct the Solution: While the previous step can give you the maximum subarray sum up to every index, the overall maximum subarray sum can be found by iterating through the dp array. maxSubarraySum = max(dp[0], dp[1], ..., dp[n-1])
    1. OR we can use max variable to track the max in dp array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int maxSubArray(int[] nums) {
	int n = nums.length;
	int[] dp = new int[n]; // dp[i] means the maximum subarray ending with nums[i]
	dp[0] = nums[0];
	int max = dp[0];

	for (int i = 1; i < n; i++) {
		dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
		max = Math.max(max, dp[i]);
	}

	return max;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4 - Divide and Conquer

We can also use Divide and Conquer:

  1. Task is to find out subarray which has the largest sum. So we need to find out the 2 indexes (left index and right index) between which the sum is maximum.
  2. Divide array into left half and right half.
  3. Conquer by recursively find maximum subarray sum for the left and right.
  4. Combine or merge the following possibilities as final result:
    1. Maximum subarray sum in the left half (Left index and right index both are in left half of the array).
    2. Maximum subarray sum in the right half. (Left index and right index both are in right half of the array).
    3. Maximum subarray sum that crosses the dividing line. (Left index in the and left half of the array and right index in right half of the array).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public int maxSubArray(int[] nums) {
	if (nums.length == 0) { // if length = 0, return 0
		return 0;
	}
	
	return maxSubArray(nums, 0, nums.length - 1);
}


public int maxSubArray(int[] nums, int start, int end) {
	if (start == end) {
		return nums[start]; // if only one element, return that
	}

	int mid = start + (end - start) / 2;
	int leftMaxSum = maxSubArray(nums, start, mid);
	int rightMaxSum = maxSubArray(nums, mid + 1, end);

	// Let's calculate the part where the subarray will start in the left half and end in the right half
	int sum = 0;
	int leftMidMax = 0;

	for (int i = mid; i >= start; i--) {
		sum += nums[i];

		if (sum > leftMidMax) {
			leftMidMax = sum;
		}
	}

	sum = 0;
	int rightMidMax = 0;

	for (int i = mid + 1; i <= end; i++) {
		sum += nums[i];

		if (sum > rightMidMax) {
			rightMidMax = sum;
		}
	}

	int centerSum = leftMidMax + rightMidMax;
	return Math.max(centerSum, Math.max(leftMaxSum, rightMaxSum));
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(log n)