Data Structures and Algorithms in Java – Arrays – Maximum Subarray

Problem:

Given an integer array find the continuous sub array with the maximum sum in the array.

Input:

For example , consider the input

[5,-6,8,-4,-2,7,4,-1]

There are many possible continuous sub arrays in the above array [5],[5,-6] , [5,-6,8] , [-6,8,-4,-2] etc. The elements just need to be continuous as present in the initial array. Even a single element can be considered a sub array . The entire array can also be considered as one of the sub arrays.

You need to add the values of all the elements in a sub array and find out which subarray has the maximum sum

Output:

In the above case the maximum sub array is [8,-4,-2,7,4] with the sum 13. All other sub arrays have a value less than 13.

So output is 13

Try out the solution here:

https://leetcode.com/problems/maximum-subarray/

Solution:

The brute force solution to this problem is to iterate through the entire array and for each element in the array add subsequent elements in the array and calculate the sum noting the maximum sum at each addition.

This requires two nested for loops and the order of complexity is O(n2)

Here is the code:

public static int maxSubArray(int[] nums) {
           
        //initialize max to first element
		int max = nums[0];

		for (int i = 0; i < nums.length; i++) {

			int sum = nums[i];

            // compare first element if it is greater than max
			if (sum > max) {

				max = sum;
			}
            //add rest of the elements one by one and at each addition check //if the sum is greater than max
			for (int j = i + 1; j < nums.length; j++) {

				sum = sum + nums[j];

				if (sum > max) {

					max = sum;

				}

			}
		}

		return max;
	}

A better solution of time complexity O(n) can be implemented using Kadane’s algorithm.

Advertisements

Hint:

The basic idea of Kadane’s algorithm is to find positive sub arrays (whose sum adds upto a positive value) and find the subarray with the maximum sum.

ALGORITHM:

STEP1: Initialize two variables , currentMax and max to 0. The currentMax refers to the sum of the current positive sub array and max refers to the sum of the largest positive sub array.

STEP2: For each element in the array , add the element to currentMax and assign it to currentMax itself

STEP2 a: If the above sum is less than 0, assign the value 0 to currentMax

STEP2 b: If currentMax calculated in STEP2 is greater than max assign max to currentMax

STEP3: Kadane’s algorithm works only if there is atleast one positive value in the array. To check this have a boolean variable and assign it to true if any element is positive (Do this along with the iteration mentioned in STEP 2)

STEP3 a: If there is any positive value as computed in STEP3 , find the maximum value from all the negative values and return it.

Let’s see how this works

Consider the array

input = [5,-6,8,-4,-2,7,4,-1]

let

i denote the index of each element

currentMax denote the sum of the current positive sub array

max denote the sum of the largest positive sub array

Iteration 1:

i=0 , input[0] = 5, currentMax = 0, max =0

currentMax = currentMax + input[0] = 0+5 = 5

It is a positive value , so assign it to currentMax, now currentMax = 5

This value is greater than max (initialized to 0) , so assign it to max , max = currrentMax = 5

Iteration 2:

i = 1; input[1] = -6, currentMax = 5, max = 5

currentMax = currentMax+input[1] = 5+(-6) = -1

It is a negative value , so assign 0 to currentMax , now currentMax = 0;

This value is less than max , hence max remains same , max = 5

Iteration 3:

i=2, input[2] = 8, currentMax = 0, max = 5

currentMax = currentMax+input[2] = 0+8 = 8

It is a positive value , so assign it to currentMax , now currentMax = 8;

This value is greater than max , hence max now becomes , max = 8

Iteration 4:

i=3 , input[3] = -4 , currentMax = 8 , max = 8

currentMax = currentMax + input[3] = 8 + (-4) = 4

It is a positive value , so assign it to currentMax , now currentMax = 4

This value is less than max , so max remains , max = 8

Iteration 5:

i = 4, input[4]= -2 , currentMax = 4, max = 8

currentMax = currentMax + input[4] = 4 + (-2) = 2

It is a positive value , so assign it to currentMax , now currentMax = 2

This value is less than max , so max remains , max = 8

Iteration 6:

i = 5, input[5] = 7 , currentMax = 2, max = 8

currentMax = currentMax + input[5] = 2+7 = 9

It is a positive value , so assign it to currentMax , now currentMax = 9

This value is greater than max , so max now becomes , max = 9

Iteration 7:

i =6, input[6] = 4, currentMax = 9, max = 9

currentMax = currentMax + input[6] = 9+4 = 13

It is a positive value , so assign it to currentMax , now currentMax = 13

This value is greater than max , so max now becomes , max = 13

Iteration 8:

i = 7, input[i] = -1 , currentMax = 13 , max = 13

currentMax = currentMax + input[7] = 13+(-1) = 12

It is a positive value , so assign it to currentMax , now currentMax = 12

This value is less than max , so max remains , max = 13

The iterations end and we return the max value , max = 13

Advertisements

Optimal Code:

Here is the code:

class Solution {
    public int maxSubArray(int[] nums) {
        
        
        
        int max = 0;
        int currentMax = 0;
        
        boolean anyPositive = false;
        
        for(int i=0;i< nums.length;i++){
            
            
            currentMax = currentMax + nums[i];
            
            
            
            if(currentMax < 0){
                
                currentMax = 0;
            }
            
            if(currentMax > max){
                
                max = currentMax;
            }
            
            if(nums[i]>0){
                
                anyPositive = true;
            }
            
            
        }
        
        
        if(!anyPositive){
            
            
            int negativeMax = nums[0];
            for(int i=0;i<nums.length;i++){
                
                
                if(nums[i] > negativeMax){
                    
                    negativeMax = nums[i];
                }
                
            }
            
            max = negativeMax;
        }
        return max;
    
    }
}

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s