Backjun-2559(数列)

10248 ワード
baekjoon テキストリンク
質問元:https://www.acmicpc.net/problem/2559
質問する

  • 毎朝9時に学校で測定した温度がある整数の数列の場合、数日連続の温度の和が最大です.

  • 例えば、10日間の温度が与えられた場合、以下のようになる.

  • 3 -2 -4 -9 0 3 7 13 8 -3

  • 2日間連続したすべての温度の和は以下の通りである.

  • このとき、温度の和の最大値は21です.

  • もう1つの例は、上記温度が与えられた場合、5日間連続したすべての温度の和を以下に示す.

  • このとき、温度の和の最大値は31である.

  • 毎日測定される温度が整数の数列に与えられる場合、数日連続の温度の和の最大値を計算するプログラムを作成します.
    • import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int K = Integer.parseInt(tokenizer.nextToken());
        tokenizer = new StringTokenizer(reader.readLine());
        int[] temp = new int[N];
        for (int i = 0; i < N; i++) {
            temp[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int answer = Integer.MIN_VALUE;

        int sum = 0;

        // 최초 합
        for (int i = 0; i < K; i++) {
            sum += temp[i];
        }

        answer = Math.max(answer, sum);

        for (int i = 1; i <= N - K; i++) {
            sum = sum - temp[i - 1] + temp[i + (K - 1)];
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }

}
  • が連続して行われたK日の中で最大の日を見つけなければならない.
  • まずK個和を最初から求める.
  • それから1つの格を移動して、左の値を除いて、右の値を加えて、最低価格を探します.
  • 最初は間違った問題を理解していて、長い時間がかかりました...
    • SWEA 5356議席の縦説(Python)
    1250000000 Key/Value Pairs in Redis 2.0.0-rc 3 on a 32 GB Machine【回転】