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

Question

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 );

Answer 1

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 );

Answer 2

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.