长度和最长增加的子序列的总和

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 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。

有人能发现我的错误吗？

Answer 1

您正在重置的length和sum只有当你发现下一个最长的序列，但你应该测试完的顺序每次重新设置：眼下

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

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

如果我们输入类似（第一输入与1小号替代两个0 S）：

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

输出是：

sum is 21 length is 6 

但总和应22

在实际上，稍微更简洁的方法是在循环开始时执行初始化测试变量，而不是initializi纳克循环外，然后里面正在重置：

// ... 
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使用尽可能小的整数允许计数负数为好。