【白俊】1912号:連合

11261 ワード
Java アルゴリズム#アルゴリズム# DP テキストリンク
Algolgolgolgolgolgolgolgolgolgolgolgolgordonのこの問題の前の連続2つの問題を2つの問題で先に解いた.
この問題.

こんな問題です.
連続と中の最高価格を探すには、以下の手順に従います.
前の
  • の結果に追加、または
  • から、連続数.
    • このような2つの選択肢があります.繰り返し文では,この2つのオプションのうちより大きなものをdpに保存すればよい.これは簡単な問題です.私が間違っている理由は
    1つ以上を選択することが条件です.😱
    ループ文でdpを求めた後、その配列の最値を出力することはできません.返事の中で答えを更新します.もう一つ似たような質問があります!👉🏻 最大減少数列
    すると、自動的に全て負数となる数列のうち、その数列の最値はmaxに格納される.
    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj1912 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        StringTokenizer st = new StringTokenizer(in.readLine());
        int[] seq = new int[N+1];
        for(int i = 1; i <= N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[N+1];
        int sol = seq[1]; // 무조건 하나는 골라야한다고 했으니까 첫 원소로 지정해주고
        for(int i = 1; i <= N; i++) {
            dp[i] = Math.max(dp[i-1]+seq[i], seq[i]);
            sol = Math.max(sol, dp[i]); // 계속 갱신한다.
        }
        System.out.println(sol);
    }
}
    最初はそうしなかった.
    int[] dp = new int[N+1];
for(int i = 1; i <= N; i++) {
    dp[i] = Math.max(dp[i-1]+seq[i], seq[i]);
}
String sol = Integer.toString(Arrays.stream(dp).max().getAsInt());
    アルゴリズム:ダブルポインタ
    [Oracle]単一関数-一般関数