CODEWITHSUNDEEP
java
Mayur Tolani
Mayur Tolani

Reputation: 1487

how to find a subarray with maximum sequence sum in java?

If the array is {-1 3 -1 9 4 -4}. I want the output as

"The sum is 15 and the array is {3 -1 9 4}."

I have the code for the sum, but how to go about for getting this subarray?

here is the code for the sum

    int maxSum = 0, thisSum = 0;
    for( int j = 0; j < a.length; j++ ){
        thisSum += a[ j ];
        if( thisSum > maxSum ){
            maxSum = thisSum; 
        }
        else if( thisSum < 0 )
            thisSum = 0;
    }
    System.out.println( maxSum );

Upvotes: 0

Views: 282

Answers (2)

Amin J
Amin J

Reputation: 1209

Just remember when from and to are 0 and sum is zero it could mean you have an empty subarray (say all are negatives).

    int []a = {-1, 3, -1, 9, 4, -4};

    int from=0, to=0;

    int maxSum = 0, thisSum = 0, thisFrom = 0 ;
    for( int j = 0; j < a.length; j++ ){

      if (thisSum == 0){ thisFrom = j ; }

        thisSum += a[ j ];
        if( thisSum > maxSum ){
            from = thisFrom;
            to = j;
            maxSum = thisSum; 
        }
        else if( thisSum < 0 )
            thisSum = 0;
    }
    System.out.println(Arrays.toString(Arrays.copyOfRange(a, from, to+1)));
    System.out.println( maxSum );

Upvotes: 1

Waqas Memon
Waqas Memon

Reputation: 1249

If you have the sum, it means at some point in your code, your code knows the greatest value it has to that point. Why dont you save the sequence in a String for each sum, and replace the string with next sequence each time you have a greatest sum and in the end you will have the sequence whose sum value is already in your maxSum variable.

Upvotes: 0

Related Questions