CODEWITHSUNDEEP
javaalgorithmsubsequence
Yoda
Yoda

Reputation: 18068

Length and sum of longest increasing subsequence

I wanted to count sum and length of the longest subsequence in the given array t.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class so {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        br.close();
        int[] t = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            t[i] = Integer.parseInt(s[i]);
        }
        int length = 1;
        int sum = t[0];
        int maxSum = 0;
        int maxLength = 0;

        for (int i = 1; i < t.length; i++) {
            for (; i < t.length && t[i - 1] <= t[i]; i++) {
                length++;
                sum += t[i];
                System.out.print(t[i] + " ");
            }

            if (length > maxLength) {
                maxLength = length;
                maxSum = sum;
                length = 1;
                sum = 0;
                i--;
            }
        }
        System.out.println("sum is " + maxSum + " length is " + maxLength);
    }
}

for the numbers1 1 7 3 2 0 0 4 5 5 6 2 1 I get output:

sum is 20 length is 6

but for the same numbers in reverse order 1 2 6 5 5 4 0 0 2 3 7 1 1 I get output:

sum is 17 length is 6 which is not true because I should get sum is 12 length is 5.

Could someone spot the my mistake?

Upvotes: 2

Views: 296

Answers (1)

nem035
nem035

Reputation: 35481

You are reseting the length and sum only when you find the next longest sequence but you should reset them every time you finish testing a sequence:

Right now, your code accumulates length and sum until it surpasses maxLength but length and sum are test variables that need to be reset when testing each possible subsequence.

Furthermore, you sum variable needs to reset to the current test value at t[i - 1] and not to 0. The reason you are getting a correct result even though this bug is present is because the first item in the LIS for both of your inputs is 0.

If we input something like (replace two 0s in the first input with 1s):

1 1 7 3 2 1 1 4 5 5 6 2 1

Output is: 

sum is 21 length is 6

But sum should be 22

In fact, a slightly cleaner way would be to perform initialization of your test variables at the beginning of the loop instead of initializing outside of the loop and then reseting inside:

// ...
int length, sum, maxSum = Integer.MIN_VALUE, maxLength = Integer.MIN_VALUE;

for (int i = 1; i < t.length; i++) {
   // initialize test variables
   length = 1;
   sum = t[i - 1];
   for (; i < t.length && t[i - 1] <= t[i]; i++) {
       length++;
       sum += t[i];
       System.out.print(t[i] + " ");
   }

   if (length > maxLength) {
       maxLength = length;
       maxSum = sum;
       i--;
   }
}
// ...

NOTE: I added initialization for maxLength and maxSum to use the smallest possible integer to allow counting negative numbers as well.

Upvotes: 2

Related Questions