Maximum Subarray

Tags: leetcode dp java python

There's an interesting problem I recently solved on leetcode based on dynamic programming. My Github repository contains list of all problems that I have solved. I often start with a brute force approach without fretting about time complexity. Later I try to improve my algorithm for a better efficient solution.

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

Brute force algorithm

We can commence with a brute force algorithm. For every element of array, we compare its sum with the rest of the element to calculate maximum sum.

• Java
• Python

	class Solution {
	public int maxSubArray(int[] nums) {
	if (nums.length == 1){
	return nums[0];
	}
	int output = nums[0];
	for (int i = 0; i < nums.length; i++) {
	int tempSum = nums[i];
	for (int j = i + 1; j < nums.length; j++) {
	tempSum += nums[j];
	output = Math.max(tempSum, output);
	}
	output = Math.max(output, nums[i]);
	}
	return output;
	}
	}

view raw BruteMaxSubArray.java hosted with ❤ by GitHub

	class Solution:
	def maxSubArray(self, nums: List[int]) -> int:
	if len(nums) == 1:
	return nums[0]
	output_sum = nums[0]
	for i in range(0, len(nums)):
	temp_sum = nums[i]
	for j in range(i + 1, len(nums)):
	temp_sum += nums[j]
	output_sum = max(output_sum, temp_sum)
	output_sum = max(output_sum, nums[i])
	return output_sum

view raw brute_max_sub_array.py hosted with ❤ by GitHub

Time complexity is O(n²) and has Time Limit Exceeded on leetcode.

More efficient solution

We can use Kadane algorithm to solve. It scans the given array A[1..n] from left to right. In the jth step, it computes the subarray with the largest sum ending at j; this sum is maintained in variable cSum. It computes the subarray with the largest sum anywhere in A[1..j], maintained in variable oSum;

• Java
• Python

	class Solution {
	public int maxSubArray(int[] nums) {
	if (nums.length == 1){
	return nums[0];
	}
	int cSum = nums[0];
	int oSum = nums[0];
	for (int i = 1; i < nums.length; i++){
	if (nums[i] > nums[i] + cSum) {
	cSum = nums[i];
	} else {
	cSum += nums[i];
	}
	oSum = Math.max(oSum, cSum);
	}
	return oSum;
	}
	}

view raw MaximumSubArray.java hosted with ❤ by GitHub

	class Solution:
	def maxSubArray(self, nums: List[int]) -> int:
	if len(nums) == 1:
	return nums[0]
	output_sum = nums[0]
	current_sum = nums[0]
	for i in range(1, len(nums)):
	if (current_sum + nums[i] < nums[i]):
	current_sum = nums[i]
	else:
	current_sum += nums[i]
	output_sum = max(output_sum, current_sum)
	return output_sum

view raw max_sub_array.py hosted with ❤ by GitHub

The time complexity is O(n).

Footnotes

---

1. Leetcode

   ↩

2. Github Repository

   ↩

---