To Find the a subsequence of number having maximum sum in an array of numbers with positive negative values

Lets know the boundary conditions of the problem first

case 1:
If in negative plane:
conditions :
a. ) If the sum is negative.
keep treack of 2 variables :
1. downfall index ( index at which downfall started from a postive, i.e if the sum is negative )
2. upward index ( index at which upward movement began. i.e just check if the next number is postive )
if upward movement then sum=a[upwardindex]

case 2:
If in positive plane
keep adding as long the sum is positive

Case 3: Analysing transition periods

1. transition from positive plane to negative plane
sum till now of postive plane needs to stored as last_postive_sum

as long we keep moving in the negative plane there is no point in updating this last sum
as it can never increase with negative numbers.

2. But as soon as a trnasition again occurs from negative to positive i.e as sooon as a positive number is found
then new sum is the this found

3. At what time should we compare current_positive_sum and last_positive_sum
a. When a transition occurs from postive plane to negative. i.e when the downindex is freshly updated
then if current_postive_sum > last_positive_sum
then last_positive_Sum = current_positive_sum

4. The whole problem should be analysed by making a graph with y-axis, extending both in neg and posittive directions
values of y-axis are the array values
X-axis is the index of the array



/**
* @author Nitesh
*/
public class MaxSumInArray {

public static int maxSum( int[] in ) {
if ( in.length == 1 ) {
return in[0];
}
int negativeMax = in[0];
boolean notfound = true;
int i = 0;
for ( i = 1; i < in.length; i++ ) {

if ( in[i] < 0 && notfound ) {
if ( in[i] > negativeMax ) negativeMax = in[i];
continue;
}
notfound = false;
break;

}

if ( notfound && in[0] < 0 ) {
System.out.println( "all number are negative. Returning min negative");
return negativeMax;
}
if ( in[0] >= 0 ) {
i = 0;
}
System.out.println("Got the first postitive index :" + i + " , number=" + in[i] );

int current_max = in[i];
int last_max = current_max;
int downfall_index = -1;
int upward_iundex = -1;

for ( int j = i+1; j < in.length ; j++ ) {

/* first check the transition from negative plane to postive plane *
* in that case
* conditions :
* downward_index > -1
* and a[j] > 0
*/
if ( in[j] >= 0 && downfall_index > -1 ) {
downfall_index = -1;
current_max = in[j];
if ( current_max > last_max ) {
last_max = current_max;
}
continue;
}


/*
* If already moving in the negative plane then no need
* to update any pointer, either current_max, last_max, or any index
* condition :
* downward_index > -1
* and
* in[j] < 0
*/
if ( in[j] < 0 && downfall_index > -1 ) {
continue;
}

int t = current_max;
current_max += in[j];

/**
* If in positive plane then just update last max
* and continue
*/
if ( current_max >= 0 ) {
if ( current_max > last_max ) last_max = current_max;
continue;
}


/*
* if transition from positive plane to negative plane, i.e new_sum < 0 ?
*/

assert (current_max < 0 && downfall_index == -1);

if ( current_max < 0 && downfall_index == -1 ) {
downfall_index = j;
// now update last_max, i.e current_max might now be last_max
if ( t > last_max ) last_max = t;

}else {
System.out.println("Something wrong in ALGO ");
}

}

return last_max;
}

public static void main( String[] args ) {
int in[] = { 15,10, -3, -4, -5 }; // 25 ok ... pos, neg

int in1[] = { -3,-1,-22, -3, -4, -5 }; // -1 ok .... only negative

int in2[] = { 10, 13, -4, -6, 22, 1, -17, -19, 2 }; // 36 ok.. pos, neg, pos..

int in3[] = { 6,-11,-10,5 }; // 6 ok... pos, negative plane, positive plane

int max = maxSum( in3 );
System.out.println( "max=" + max );
}

}