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

次に長いシーケンスが見つかった場合にのみlengthandをリセットしていますが、シーケンスのテストを終了するたびにそれらをリセットする必要があります。sum

現在、コードは and を超えるまで累積lengthしsumますmaxLengthが、lengthandsumは、考えられる各サブシーケンスをテストするときにリセットする必要があるテスト変数です。

さらに、変数は ではなくsumで現在のテスト値にリセットする必要があります。このバグが存在するにもかかわらず、正しい結果が得られる理由は、両方の入力に対する LIS の最初の項目が であるためです。t[i - 1]00

0次のように入力すると (最初の入力の2 つの s を s に置き換えます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、可能な限り最小の整数を使用して、負の数もカウントできるようにしました。

于 2015-10-20T18:58:03.213 に答える