in Java, design linear algorithm that finds contiguous subsequence with highest sum

Question

this is the question, and yes it is homework, so I don't necessarily want anyone to "do it" for me; I just need suggestions: Maximum sum: Design a linear algorithm that finds a contiguous subsequence of at most M in a sequence of N long integers that has the highest sum among all such subsequences. Implement your algorithm, and confirm that the order of growth of its running time is linear.

I think that the best way to design this program would be to use nested for loops, but because the algorithm must be linear, I cannot do that. So, I decided to approach the problem by making separate for loops (instead of nested ones).

However, I'm really not sure where to start. The values will range from -99 to 99 (as per the range of my random number generating program).

This is what I have so far (not much):

public class MaxSum {

public static void main(String[] args){
    int M = Integer.parseInt(args[0]);
    int N = StdIn.readInt(); 
    long[] a = new long[N]; 
    for (int i = 0; i < N; i++) {
          a[i] = StdIn.readLong();}}}

if M were a constant, this wouldn't be so difficult. For example, if M==3:

public class MaxSum2 {

    public static void main(String[] args){
        int N = StdIn.readInt(); //read size for array
        long[] a = new long[N]; //create array of size N
        for (int i = 0; i < N; i++) { //go through values of array
              a[i] = StdIn.readLong();} //read in values and assign them to             
                                                //array indices

        long p = a[0] + a[1] + a[2]; //start off with first 3 indices

        for (int i =0; i<N-4; i++)
        {if ((a[i]+a[i+1]+a[1+2])>=p) {p=(a[i]+a[i+1]+a[1+2]);}}
                 //if sum of values is greater than p, p becomes that sum

        for (int i =0; i<N-4; i++) //prints the subsequence that equals p
        {if ((a[i]+a[i+1]+a[1+2])==p) {StdOut.println((a[i]+a[i+1]+a[1+2]));}}}}

If I must, I think MaxSum2 will be acceptable for my lab report (sadly, they don't expect much). However, I'd really like to make a general program, one that takes into consideration the possibility that, say, there could be only one positive value for the array, meaning that adding the others to it would only reduce it's value; Or if M were to equal 5, but the highest sum is a subsequence of the length 3, then I would want it to print that smaller subsequence that has the actual maximum sum.

I also think as a novice programmer, this is something I Should learn to do. Oh and although it will probably be acceptable, I don't think I'm supposed to use stacks or queues because we haven't actually covered that in class yet.

Answer 1

Here is my version, adapted from Petar Minchev's code and with an important addition that allows this program to work for an array of numbers with all negative values.

public class MaxSum4 {

public static void main(String[] args)
{Stopwatch banana = new Stopwatch(); //stopwatch object for runtime data.

    long sum = 0;
    int currentStart = 0;
    long bestSum = 0;
    int bestStart = 0;
    int bestEnd = 0;

    int M = Integer.parseInt(args[0]); // read in highest possible length of         
                                        //subsequence from command line argument. 
    int N = StdIn.readInt(); //read in length of array
    long[] a = new long[N]; 
    for (int i = 0; i < N; i++) {//read in values from standard input
          a[i] = StdIn.readLong();}//and assign those values to array
    long negBuff = a[0];

    for (int i = 0; i < N; i++) { //go through values of array to find 
                                 //largest sum (bestSum)
    sum += a[i];                  //and updates values. note bestSum, bestStart,
                                  // and bestEnd updated
    if (sum > bestSum) {          //only when sum>bestSum
        bestSum = sum; 
        bestStart = currentStart; 
        bestEnd = i; }

    if (sum < 0) { //in case sum<0, skip to next iteration, reseting sum=0
        sum = 0;   //and update currentStart
        currentStart = i + 1;
        continue; }

    if (i - currentStart + 1 == M) { //checks if sequence length becomes equal 
                                         //to M.
        do {                          //updates sum and currentStart
           sum -= a[currentStart]; 
           currentStart++;  
        } while ((sum < 0 || a[currentStart] < 0) && (currentStart <= i)); 
                        //if sum or a[currentStart]
    }                   //is less than 0 and currentStart<=i,
}                       //update sum and currentStart again

    if(bestSum==0){ //checks to see if bestSum==0, which is the case if 
                            //all values are negative
        for (int i=0;i<N;i++){ //goes through values of array 
                                          //to find largest value
            if (a[i] >= negBuff) {negBuff=a[i]; 
                                  bestSum=negBuff; bestStart=i; bestEnd=i;}}}
                              //updates bestSum, bestStart, and bestEnd

    StdOut.print("best subsequence is from 
                 a[" + bestStart + "] to a[" + bestEnd + "]: ");
    for (int i = bestStart; i<=bestEnd; i++)
    {
        StdOut.print(a[i]+ " "); //prints sequence
    }
    StdOut.println();
    StdOut.println(banana.elapsedTime());}}//prints elapsed time

also, did this little trace for Petar's code:

trace for a small array

M=2

array: length 5

index value
0      -2
1       2
2       3
3       10
4       1

for the for-loop central to program:

i = 0   sum = 0 + -2 = -2
    sum>bestSum? no
    sum<0? yes so sum=0, currentStart = 0(i)+1 = 1,
         and continue loop with next value of i

i = 1   sum = 0 + 2 = 2
    sum>bestSum? yes so bestSum=2 and bestStart=currentStart=1 and bestEnd=1=1
    sum<0? no
    1(i)-1(currentStart)+1==M? 1-1+1=1 so no

i = 2   sum = 2+3 = 5
    sum>bestSum? yes so bestSum=5, bestStart=currentStart=1, and bestEnd=2
    sum<0? no
    2(i)-1(currentStart)+1=M? 2-1+1=2 so yes: 
    sum = sum-a[1(curentstart)] =5-2=3. currentStart++=2.
    (sum<0 || a[currentStart]<0)? no 

i = 3   sum=3+10=13
    sum>bestSum? yes so bestSum=13 and bestStart=currentStart=2 and bestEnd=3
    sum<0? no
    3(i)-2(currentStart)+1=M? 3-2+1=2 so yes: 
        sum = sum-a[1(curentstart)] =13-3=10. currentStart++=3.
        (sum<0 || a[currentStart]<0)? no 

i = 4   sum=10+1=11
    sum>bestSum? no
    sum<0? no
    4(i)-3(currentStart)+1==M? yes but changes to sum and currentStart now are 
        irrelevent as loop terminates

Thanks again! Just wanted to post a final answer and I was slightly proud for catching the all negative thing.

Answer 2

Each element is looked at most twice (one time in the outer loop, and one time in the while loop).

O(2N) = O(N)

Explanation: each element is added to the current sum. When the sum goes below zero, it is reset to zero. When we hit M length sequence, we try to remove elements from the beginning, until the sum is > 0 and there are no negative elements in the beginning of it.

By the way, when all elements are < 0 inside the array, you should take only the largest negative number. This is a special edge case which I haven't written below.

Beware of bugs in the below code - it only illustrates the idea. I haven't run it.

int sum = 0;
int currentStart = 0;

int bestSum = 0;
int bestStart = 0;
int bestEnd = 0;

for (int i = 0; i < N; i++) {
    sum += a[i];
    if (sum > bestSum) {
        bestSum = sum; 
        bestStart = currentStart; 
        bestEnd = i;
    }

    if (sum < 0) {
        sum = 0; 
        currentStart = i + 1;
        continue;
    }

    //Our sequence length has become equal to M
    if (i - currentStart + 1 == M) { 
        do {
           sum -= a[currentStart]; 
           currentStart++;  
        } while ((sum < 0 || a[currentStart] < 0) && (currentStart <= i)); 
    }
}

Answer 3

I think what you are looking for is discussed in detail here

Find the subsequence with largest sum of elements in an array

I have explained 2 different solutions to resolve this problem with O(N) - linear time.