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:

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^2)
  • Kadane’s algorithm - O(n)
  • Dynamic Programming - O(n), Space complexity - O(n)
  • Divide and Conquer

Method 1 - Brute Force

Naive solution would be use two for loops and check every subarray and return the subarray which has the maximum sum.

Time Complexity: O(N^2)

Method 2 - Kadane’s Algorithm 🏆

Kadane’s Algorithm for Maximum Subarray Sum

Complexity

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

Method 3 - 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

Java
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

Java
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));
}