長度和最長增加的子序列的總和

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使用盡可能小的整數允許計數負數爲好。