java - 最长递增子序列的长度和总和

Question

我想计算给定数组 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);
    }
}

对于数字1 1 7 3 2 0 0 4 5 5 6 2 1 我得到输出:

sum 为 20 长度为 6

但对于相反顺序的相同数字 1 2 6 5 5 4 0 0 2 3 7 1 1 我得到输出:

sum is 17 length is 6 这是不正确 因为我应该得到 sum is 12 length is 5。

有人能发现我的错误吗？

Answer 1

您正在重置length 和sum仅当您找到下一个最长序列时但您应该每次 你完成了一个序列的测试:

现在，您的代码累积 length 和 sum 直到它超过 maxLength 但 length 和 sum 是在测试每个可能的子序列时需要重置的测试变量。

此外，您的sum 变量需要重置为t[i - 1] 的当前测试值，而不是0。即使存在此错误，您仍获得正确结果的原因是，您的两个输入的 LIS 中的第一项都是 0。

如果我们输入类似的内容(将第一个输入中的两个 0 替换为 1):

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

输出是:

sum is 21 length is 6

但是总和应该是22

事实上，一种稍微更简洁的方法是在循环开始时执行测试变量的初始化，而不是在循环外初始化然后在循环内重置:

// ...
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--;
   }
}
// ...

注意:我为 maxLength 和 maxSum 添加了初始化，以使用可能的最小整数来计算负数。