2

我想计算给定数组中最长子序列的总和和长度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 is 20 length is 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.

有人能发现我的错误吗？

4

1 回答 1

2

仅当您找到length下一个最长的序列时才重置它们，但每次完成测试序列时都应重置它们：sum

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

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

如果我们输入类似的内容（将0第一个输入中的两个 s替换为1s）：

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使用尽可能小的整数来允许计算负数。

于 2015-10-20T18:58:03.213 回答