CODEWITHSUNDEEP
javaalgorithmkadanes-algorithm
Aqib Saeed
Aqib Saeed

Reputation: 125

How to return maximum sub array in Kadane's algorithm?

public class Kadane {
  double maxSubarray(double[] a) {
    double max_so_far = 0;
    double max_ending_here = 0;

    for(int i = 0; i < a.length; i++) {
      max_ending_here = Math.max(0, max_ending_here + a[i]);
      max_so_far = Math.max(max_so_far, max_ending_here);
    }
    return max_so_far;
  }
}

The above code returns the sum of the maximum sub-array.

How would I instead return the sub-array which has the maximum sum?

Upvotes: 9

Views: 13128

Answers (10)

raghavreddy
raghavreddy

Reputation: 11

Update the max_start_index and max_end_index when we indeed got the max_so_far. start_index keeps changing so, keep track of it and store it into max_start_index when you found max.

class Solution {
    public int maxSubArray(int[] nums) {
        int max_so_far = nums[0];
        int max_end_here = nums[0];
        int max_start_index = 0;
        int start_index = 0;
        int max_end_index = 0;
        for (int i=1; i<nums.length; i++) {
            max_end_here = max_end_here + nums[i];
            if (max_end_here<0) {
                start_index = i+1;
                max_end_here=0;
            }
            if (max_so_far < max_end_here) {
                max_start_index = start_index;
                max_end_index = i;
                max_so_far = max_end_here;
            }
        }
        System.out.println("i="+max_start_index+";j="+max_end_index);
        return max_so_far;
        
    }
}

Upvotes: 0

mikey
mikey

Reputation: 5160

Something like this:

public class Kadane {
  double[] maxSubarray(double[] a) {
    double max_so_far = a[0];
    double max_ending_here = a[0];
    int max_start_index = 0;
    int startIndex = 0;
    int max_end_index = -1;

    for(int i = 1; i < a.length; i++) {
      if(a[i] > max_ending_here +a[i]) {
        startIndex = i;
        max_ending_here = a[i];
      }
      else {
        max_ending_here += a[i];
      }

      if(max_ending_here > max_so_far) {
        max_so_far = max_ending_here;
        max_start_index = startIndex;
        max_end_index = i;
      }
    }

    if(max_start_index <= max_end_index) {
      return Arrays.copyOfRange(a, max_start_index, max_end_index+1);
    }

    return null;
  }
}

UPDATE by the OP: also handle the cases with all negative numbers in the array and default of the sum is 0.

Upvotes: 12

Mijo Tvrdojevic
Mijo Tvrdojevic

Reputation: 1

Another implementation in C++, both Kadane (which is actually just dynamic programming approach) and extended Kadane with indices calculation and some comments:

    int maxSubArray(vector<int>& nums) 
    {        
        int n = nums.size();
        
        if(n == 0) return INT_MIN;
        
        // max sum that ends at index I
        int sumMaxI = nums[0];
        
        // total max sum
        int sumMax = nums[0];
        for(int i = 1; i < n; i++)
        {  
            int curr = nums[i];
            
            // calc current max sum that ends at I
            int currSumMaxI = sumMaxI + curr;
            
            // calc new max sum that ends at I
            sumMaxI = max(currSumMaxI, curr);
            
            // calc new total max sum
            sumMax = max(sumMax, sumMaxI);
        }
        
        return sumMax;
    }    
    
    
    int maxSubArray_findBeginEnd(vector<int>& nums) 
    {        
        int n = nums.size();
        
        if(n == 0) return INT_MIN;
        
        // max sum that ends at index I
        int sumMaxI = nums[0];
        // start index for max sum (end index is I)
        int sumMaxIStart = 0;
                
        // total max sum
        int sumMax = nums[0];
        // start and end index for total max sum
        int sumMaxStart = 0;
        int sumMaxEnd = 0;
        for(int i = 1; i < nums.size(); i++)
        {  
            int curr = nums[i];
            
            // calc current max sum that ends at I
            int currSumMaxI = sumMaxI + curr;
            
            // calc new min sum that ends at I and its starting index
            // this part is equal to: sumMaxI = max(currSumMaxI, curr);
            // but additionaly enables to save new start index as well
            if(curr > currSumMaxI)
            {
                sumMaxI = curr;
                sumMaxIStart = i;
            }
            else
                sumMaxI = currSumMaxI;
                 
            // calculate total max sum
            // this part is equal to: sumMax = max(sumMax, sumMaxI);
            if(sumMaxI > sumMax)
            {
                sumMax = sumMaxI;
                sumMaxStart = sumMaxIStart;
                sumMaxEnd = i;
            }
            // this part is to additionaly capture longest subarray among all that have max sum
            // also, of all subarrays with max sum and max len, one with smallest index
            // will be captured
            else if(sumMaxI == sumMax) 
            {
                if(i - sumMaxIStart > sumMaxEnd - sumMaxStart)
                {
                    sumMaxStart = sumMaxIStart;
                    sumMaxEnd = i;
                }
            }
        }
        
        // check validity of start and end indices
        int checkSum = 0;
        for(int i = sumMaxStart; i <= sumMaxEnd; i++)
            checkSum += nums[i];
        assert(checkSum == sumMax); 
        
        // output indices
        cout << "Max subarray indices: [" << sumMaxStart << "," << sumMaxEnd << "]" << endl;
        
        return sumMax;
    }

Upvotes: 0

Hani Ewais
Hani Ewais

Reputation: 144

I know this is an old thread, but wanted to share my version of the solution for clarity.

  • sumMax is the variable storing the maxSubArray sum
  • subSum is the temporary variable used to compare if sum increased or not.
  • We know that we should move the lower bound only if subSum has started over
public static int maxSubArray(int[] a, out int[] subArr){
        int sumMax = int.MinValue;
        int subSum = 0;
        int iLow = 0, iHigh = 0;
        for(int i=0; i<a.Length; i++){
            subSum+=a[i];
            if(subSum>sumMax){
                sumMax = subSum;
                //move high (upper bound) since sumMax increased 
                iHigh = i;
                
                //if the subSum is new, then move lower bound
                if(subSum == a[i]){
                    iLow = i;
                }
            }
            subSum = Math.Max(subSum, 0);
        }
        
        //build the array - returned as an out parameter
        int index = 0;
        subArr = new int[iHigh-iLow+1];
        while(iLow <= iHigh){
            subArr[index++] = a[iLow++];
        } 
        
        return sumMax;
    }

Upvotes: 0

javaProf
javaProf

Reputation: 31

private static int[] applyKadaneAlgorithmGetSubarrayOptimized(int[] input) {
    int localMax = input[0];
    int globalMax = input[0];
    int start = 0;
    int end = 0;
    for (int i = 1; i < input.length; i++) {
        localMax = Math.max(localMax + input[i], input[i]);
        if(localMax == input[i]) { //this is similar as --> input[i] > (localMax + input[i])
            start = i;
        }
        if(localMax > globalMax) {
            end = i;
        }
        globalMax = Math.max(localMax, globalMax);
    }

    //Below condition only occur`enter code here`s when all members of the array are negative integers
    //Example: {-9, -10, -6, -7, -8, -1, -2, -4}
    if(start > end) {
        start = end;
    }

    return Arrays.copyOfRange(input, start, end + 1);
}

Upvotes: 0

Kushal Mondal
Kushal Mondal

Reputation: 111

Update the probable left(starting) index every time a new sub-array sum is initiated. Update the final left and right(ending) once the max_sum is updated. Also maintain a trigger that tells if a new sub-array sum is created. 

int last = 0;
    int sum  = Integer.MIN_VALUE;
    boolean fOrReset = true;
    int _L = -1, L = -1, R = -1;

    for (int j = 0; j < arr.length; j++) {
        last += arr[j];
        if (fOrReset) {
            _L = j+1;
        }
        fOrReset = false;
        if (sum < last) {
            sum = last;
            L = _L;
            R = j+1;
        }
        if (last < 0) {
            last = 0;
            fOrReset = true;
        }
    }

Upvotes: 0

optional
optional

Reputation: 3350

we can keep track max subarray by using following code :

import java.util.Arrays;

public class KadaneSolution4MaxSubArray{

    public static void main(String[]args){
        int [] array = new int[]{13,-3,-25,20 ,-3 ,-16,-23,18,20,-7,12,-5,-22,15,-4,7};

        int[] maxSubArray = maxSubArrayUsingKadaneSol(array);
        for(int e : maxSubArray){
                System.out.print(e+"\t");
            }
        System.out.println();
    }

    public static int[] maxSubArrayUsingKadaneSol(int array[]){
        long maxSoFar =array[0];
        long maxEndingHere =array[0];
        int startIndex = 0;
        int endIndex =0;
        int j=1;
        for(; j< array.length ;j++){
            int val = array[j];
            if(val >= val+maxEndingHere){
                    maxEndingHere = val;
                    startIndex = j;
                }else {
                    maxEndingHere += val;
                    };
            if(maxSoFar < maxEndingHere){
                    maxSoFar = maxEndingHere;
                    endIndex = j;
                }
            }

            return Arrays.copyOfRange(array,startIndex,endIndex+1);
    }   
}

P.S. Assume that given array is candidate of Max sub array problem as well as not having all elements negative

Upvotes: 0

Saras Arya
Saras Arya

Reputation: 3112

A more easier approach closely linked to the algorithm.

int main()
{
   int a[]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
   int size=sizeof(a)/sizeof(a[0]);
   int startIndex=0,endIndex=0,i,j;
   int max_so_far=0,max_sum=-999;
   for(i=0;i<size;i++)
   {
   max_so_far=max_so_far+a[i];//kadane's algorithm step 1
   if(max_so_far>max_sum) //computing max
   {
      max_sum=max_so_far;
      endIndex=i;
   }

   if(max_so_far<0)
   {
   max_so_far=0;
   startIndex=i+1;
   }
}
   cout<<max_so_far<<" "<<startIndex<<" "<<endIndex;
   getchar();
   return 0;
}

Once you have start and End index.

for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}

Upvotes: 0

nathanlrf
nathanlrf

Reputation: 41

I maintain the max_so_far in a list:

for(int i = 0;i<N;i++){
    max_end_here = Math.max(seq[i], max_end_here + seq[i]);
    sum_list.add(max_end_here);
    // System.out.println(max_end_here);
    max_so_far = Math.max(max_so_far, max_end_here);
}

Then search the biggest sum in list, its index as sub sequnece end. Start from index as end and search backwards, find the last index whose value is positive. Subsequence start is this index.

for(int i=sum_list.size()-1; i>=0; i--){
    if(sum_list.get(i) == max_so_far){
        end = i;
        while(sum_list.get(i) > 0 && i>=0){
            i--;
        }
        start = (i==-1)?0:i+1;
        break;
    }
}

Upvotes: 0

Andy
Andy

Reputation: 21

The code above has an error. Should be:

max_ending_here = Math.max(a[i], max_ending_here + a[i]);

NOT:

max_ending_here = Math.max(0, max_ending_here + a[i]);

If not, would fail for a sequence such as: 2 , 4, 22, 19, -48, -5 , 20, 40 and return 55 instead of the correct answer of 60.

SEE Kadane algorithm at http://en.wikipedia.org/wiki/Maximum_subarray_problem

Upvotes: 2

Related Questions