Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## 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 ******************/
{
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)
{
}
else
{
}
return lst;
}

/************** Function to find minimum subsequence ******************/
{
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)
{
}
else
{
}
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: