[伯俊#2559]数列

14100 ワード
ダブルポインタ ps 白駿 Java boj テキストリンク

1.問題の説明



2.解説


二重for文をkに繰り返すことができますが、ここでは「二重ポインタ」メソッドを使用してアクセスしてみます.
💡 ダブルポインタ
1つのアルゴリズム
  • は、リストに順次アクセスする必要がある場合に、2つのポイントの位置を記録して処理する.
    上記の例では、[3, -2, -4, -9, 0, 3, 7, 13, 8, -3]の配列から連続して5つの和を求める場合を見てみましょう.
    通常のデュアルfor文を使用する場合は、次のようになります.
    maxSum = Math.MIN_VALUE;
for (int i = 0; i < length; i++) {
    sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += arr[j];
    }
    maxSum = max(maxSum, sum);
}
    しかし,この方法の欠点は,最初から最後まで配列の和を求めるため,長い時間がかかることである.しかし、ここでダブルポインタ技術を使うとどうなるのでしょうか.
    int maxSum = Math.MIN_VALUE;
int start = 0, end = 0
int cnt = 1, sum = arr[0]

while (end < length) {
    if (cnt == k) {
        maxSum = max(maxSum, sum);
        --cnt;
        sum -= arr[start++];
    } else {
        ++end;
        if (end < length) {
            sum += arr[end];
        }
        ++cnt;
    }
}
    ダブルポインタを用いることで、増加回数kで最大値を更新し、前の位置値をsumから減算することで、不要な演算回数を減少させることができる.
    配列の値にも負の値が含まれているため、最低価格は負の値になる可能性があります.したがって,maxSumをintの最小値(-2^31)に初期化する必要がある.

    3.正解コード

    import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(twoPointer(n, k));
    }

    static int twoPointer(int n, int k) {
        int cnt = 1, sum = arr[0], maxSum = Integer.MIN_VALUE;
        int start = 0, end = 0;

        while (end < n) {
            if (cnt == k) {
                maxSum = Math.max(maxSum, sum);
                --cnt;
                sum -= arr[start++];
            } else {
                ++end;
                if (end < n) {
                    sum += arr[end];
                }
                ++cnt;
            }
        }

        return maxSum;
    }
}
    • [白俊]14888号:挿入演算子
    [BOJ 12865]普通リュック(Python)