Make delicious recipes!

Find two contiguous subsequences in an array with maximum difference



Problem: Find two contiguous subsequences in an array with maximum difference.
The subsequences may be overlapping.


Solution: This is an extended case of Kadane's algorithm.
Here we find max-subsequence using Kadane and then the min-subsequence using Kadane.
Desired result is the difference of sums of these two subsequeces.


Code:


import java.util.ArrayList;
import java.util.List;


public class TwoSubsequencesWithMaximumDifference 
{

    // generate random input from the main function
    public static void main(String[] args) 
    {
        for (int j=1; j<=10; j++)
        {
            int arr4[] = new int[10];
            for (int i=0; i<10; i++)
                arr4[i] = ((i%j==0)?(-1):1)*((int)(10*Math.random()));
            printSubsequencesWithMaximumDifference (arr4);
        }
    }

    
    // major function to find the maximum difference between two subsequences
    static void printSubsequencesWithMaximumDifference(int[] arr) 
    {
        List <Integer> endsMax = maxKadane (arr);
        List <Integer> endsMin = minKadane (arr);
        
        // print the input and the output
        printArr (arr, "Array      : ", 0, arr.length-1);
        printArr (arr, "Max subseq : ", endsMax.get(0), endsMax.get(1));
        printArr (arr, "Min subseq : ", endsMin.get(0), endsMin.get(1));
        System.out.println();
    }
    

    /************** Function to find maximum subsequence ******************/
    static List<Integer> maxKadane(int[] arr) 
    {
        int maxSum = arr[0];
        int currSum = 0;
        
        // variables to store the start and end of the maximum and current subsequence     
        int currEnd1 = 0;
        int currEnd2 = -1;
        int maxEnd1 = 0;
        int maxEnd2 = 0;
        
        int maxIndex = 0; // stores the index of maximum element
        
        for (int i=0; i<arr.length; i++)
        {
            currSum += arr[i];
            if (currSum >= maxSum)
            {
                currEnd2 = i;
                // Update all variables associated with maximum.
                maxSum = currSum;
                maxEnd1 = currEnd1;
                maxEnd2 = currEnd2;
            }

            if (currSum <= 0)
            {
                currSum = 0;
                currEnd1 = i+1;
            }
            
            if (arr[maxIndex] < arr[i]) // find index of the maximum element
                maxIndex = i;
        }
        
        List <Integer> lst = new ArrayList <Integer>();
        if (maxSum < 0)
        {
            lst.add(maxIndex);
            lst.add(maxIndex);
        }
        else
        {
            lst.add(maxEnd1);
            lst.add(maxEnd2);
        }
        return lst;
    }
    
    
    /************** Function to find minimum subsequence ******************/
    static List<Integer> minKadane(int[] arr) 
    {
        int minSum = arr[0];
        int currSum = 0;
        
        // variables to store the start and end of the minimum and current subsequence
        int currEnd1 = 0;
        int currEnd2 = -1;
        int minEnd1 = 0;
        int minEnd2 = 0;
        
        int minIndex = 0; // stores the index of minimum element
        
        for (int i=0; i<arr.length; i++)
        {
            currSum += arr[i];
            if (currSum <= minSum)
            {
                currEnd2 = i;
                // Update all variables associated with minimum.
                minSum = currSum;
                minEnd1 = currEnd1;
                minEnd2 = currEnd2;
            }
            
            if (currSum >= 0)
            {
                currSum = 0;
                currEnd1 = i+1;
            }
            
            
            if (arr[minIndex] > arr[i]) // find index of the minimum element
                minIndex = i;
        }
        
        List <Integer> lst = new ArrayList <Integer>();
        if (minSum > 0)
        {
            lst.add(minIndex);
            lst.add(minIndex);
        }
        else
        {
            lst.add(minEnd1);
            lst.add(minEnd2);
        }
        return lst;
    }
    
    
    // helper function to print the array
    static void printArr (int arr[], String msg, int start, int end)
    {
        System.out.print("\n" + msg);
        int sum=0;
        for (int i=start; i<=end; i++)
        {
            System.out.print(arr[i] + ",");
            sum += arr[i];
        }
        System.out.print(" = " + sum);
        
    }
}



Sample Execution:


Array      : -6,-1,-4,-8,-4,-6,-1,-9,-1,-9,   SUM= -49
Max subseq : -1,   SUM= -1
Min subseq : -6,-1,-4,-8,-4,-6,-1,-9,-1,-9,   SUM= -49



Array      : -7,1,-4,2,-7,0,-7,9,-1,1,   SUM= -13
Max subseq : 9,-1,1,   SUM= 9
Min subseq : -7,1,-4,2,-7,0,-7,   SUM= -22



Array      : 0,7,5,-7,2,8,-9,3,7,-3,   SUM= 13
Max subseq : 7,5,-7,2,8,-9,3,7,   SUM= 16
Min subseq : -9,   SUM= -9



Array      : -1,2,5,7,-4,3,3,9,-6,0,   SUM= 18
Max subseq : 2,5,7,-4,3,3,9,   SUM= 25
Min subseq : -6,0,   SUM= -6



Array      : -2,5,2,1,5,-2,6,5,0,5,   SUM= 25
Max subseq : 5,2,1,5,-2,6,5,0,5,   SUM= 27
Min subseq : -2,   SUM= -2



Array      : -6,9,6,9,1,2,-9,9,0,3,   SUM= 24
Max subseq : 9,6,9,1,2,-9,9,0,3,   SUM= 30
Min subseq : -9,   SUM= -9



Array      : -4,5,2,2,8,0,5,-1,9,7,   SUM= 33
Max subseq : 5,2,2,8,0,5,-1,9,7,   SUM= 37
Min subseq : -4,   SUM= -4



Array      : 0,3,8,5,4,0,7,3,-2,1,   SUM= 29
Max subseq : 3,8,5,4,0,7,3,   SUM= 30
Min subseq : -2,   SUM= -2



Array      : -2,2,5,5,9,6,4,7,8,-2,   SUM= 42
Max subseq : 2,5,5,9,6,4,7,8,   SUM= 46
Min subseq : -2,   SUM= -2



Array      : -1,0,1,8,4,3,8,5,4,6,   SUM= 38
Max subseq : 1,8,4,3,8,5,4,6,   SUM= 39
Min subseq : -1,0,   SUM= -1







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal