Make delicious recipes!

Find two disjoint subsequences in an array with maximum difference



Problem: Find two disjoint (non-overlapping) subsequences in an array with maximum difference.


Solution: This is an extended case of Kadane's algorithm and previous problem.
Only difference is that in the previous problem, the contiguous subsequences could be overlapping but they cannot be in this case.


For every index in the array, computer max and min subsequences on either side of the index.
Find the difference between max-min pairs of these 4 subsequences and choose the max among them.

Code:


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


public class TwoDisjointSubsequencesWithMaximumDifference 
{

    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] = (Math.random() > 0.5?1:-1)*((int)(10*Math.random()));
            disjointSubsequencesWithMaximumDifference (arr4);
        }
    }

    
    static void disjointSubsequencesWithMaximumDifference(int[] arr) 
    {
        List<Integer> finalMax = null;
        List<Integer> finalMin = null;
        Integer maxDiff = null;
        
        for (int i=0; i<arr.length; i++) // foreach array index
        {
            // compute max and min subsequence from 0 to i
            List <Integer> endsMax1 = maxKadane (arr, 0, i);
            List <Integer> endsMin1 = minKadane (arr, 0, i);
            
            // compute max and min subsequence from i to end
            List <Integer> endsMax2 = maxKadane (arr, i, arr.length);
            List <Integer> endsMin2 = minKadane (arr, i, arr.length);
            
            
            // In these 4 subsequences, choose difference among max-min pairs of subsequences   
            // right max subseq with left min subseq and
            // right min subseq with left max subseq
            int diff1 = sum(arr,endsMax1) - sum(arr,endsMin2);
            int diff2 = sum(arr,endsMax2) - sum(arr,endsMin1);
            
            // Choose the pair which has bigger difference
            // And replace the finalMax ones with that if its the biggest till now
            if (diff1 > diff2) 
            {
                if (maxDiff == null || diff1 > maxDiff)
                {
                    maxDiff = diff1;
                    finalMax = endsMax1;
                    finalMin = endsMin2;
                }
            }
            else
            {
                if (maxDiff == null || diff2 > maxDiff)
                {
                    maxDiff = diff2;
                    finalMax = endsMax2;
                    finalMin = endsMin1;
                }
            }
        }
        
        
        // print the final output
        printArr (arr, "Array      : ", 0, arr.length-1);
        printArr (arr, "Max subseq : ", finalMax.get(0), finalMax.get(1));
        printArr (arr, "Min subseq : ", finalMin.get(0), finalMin.get(1));
        System.out.println();
    }
    

    /************** Function to find maximum subsequence ******************/
    static List<Integer> maxKadane(int[] arr, int start, int end) 
    {
        int maxSum = arr[start];
        int currSum = 0;
        
        // variables to store the start and end of the maximum and current subsequence    
        int currEnd1 = start;
        int currEnd2 = -1;
        int maxEnd1 = start;
        int maxEnd2 = start;
        
        int maxIndex = start; // stores the index of maximum element
        
        for (int i=start; i<end; 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])
                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 start, int end) 
    {
        int minSum = arr[start];
        int currSum = 0;
        
        // variables to store the start and end of the minimum and current subsequence    
        int currEnd1 = start;
        int currEnd2 = -1;
        int minEnd1 = start;
        int minEnd2 = start;
        
        int minIndex = start; // stores the index of minimum element
        
        for (int i=start; i<end; 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])
                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 compute array sum from index 'start' to 'end'
    static int sum(int[] arr, List<Integer> ends) 
    {
        int sum=0;
        for (int i=ends.get(0); i<=ends.get(1); i++)
            sum += arr[i];
        return sum;
    }


    // Helper function to print an array with sum from index 'start' to 'end'
    static void printArr (int arr[], String msg, int start, int end)
    {
        System.out.print("\n" + msg + "(" + start + "," + end + ") : ");
        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      : (0,9) : 4,-7,-5,-7,0,0,2,-9,-2,0,   SUM= -24
Max subseq : (0,0) : 4,   SUM= 4
Min subseq : (1,9) : -7,-5,-7,0,0,2,-9,-2,0,   SUM= -28



Array      : (0,9) : 7,-6,-2,-9,-9,5,0,0,-8,4,   SUM= -18
Max subseq : (0,0) : 7,   SUM= 7
Min subseq : (1,8) : -6,-2,-9,-9,5,0,0,-8,   SUM= -29



Array      : (0,9) : -8,5,-9,4,6,4,-2,6,-2,-7,   SUM= -3
Max subseq : (3,7) : 4,6,4,-2,6,   SUM= 18
Min subseq : (0,2) : -8,5,-9,   SUM= -12

Array      : (0,9) : 9,-9,-6,7,-5,-9,1,-8,-6,-5,   SUM= -31
Max subseq : (0,0) : 9,   SUM= 9
Min subseq : (1,9) : -9,-6,7,-5,-9,1,-8,-6,-5,   SUM= -40



Array      : (0,9) : -2,-9,5,0,4,7,5,-5,0,9,   SUM= 14
Max subseq : (2,9) : 5,0,4,7,5,-5,0,9,   SUM= 25
Min subseq : (0,1) : -2,-9,   SUM= -11



Array      : (0,9) : 0,5,5,-3,-7,-4,-2,5,7,0,   SUM= 6
Max subseq : (7,9) : 5,7,0,   SUM= 12
Min subseq : (3,6) : -3,-7,-4,-2,   SUM= -16



Array      : (0,9) : -6,-7,-5,-8,2,0,-2,-1,-3,5,   SUM= -25
Max subseq : (9,9) : 5,   SUM= 5
Min subseq : (0,8) : -6,-7,-5,-8,2,0,-2,-1,-3,   SUM= -30



Array      : (0,9) : -3,2,8,2,-4,9,-9,3,-3,-2,   SUM= 3
Max subseq : (1,5) : 2,8,2,-4,9,   SUM= 17
Min subseq : (6,9) : -9,3,-3,-2,   SUM= -11



Array      : (0,9) : -5,0,-5,-8,5,-5,3,6,9,-3,   SUM= -3
Max subseq : (6,8) : 3,6,9,   SUM= 18
Min subseq : (0,3) : -5,0,-5,-8,   SUM= -18



Array      : (0,9) : -6,-6,8,-6,2,5,4,6,0,-3,   SUM= 4
Max subseq : (2,8) : 8,-6,2,5,4,6,0,   SUM= 19
Min subseq : (0,1) : -6,-6,   SUM= -12







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