白駿#1912.れんけつ

8449 ワード
ps どうてきけいかくほう cpp 白駿 algorithm テキストリンク

白駿#1912。れんけつ

整理する


  • この問題も動的プログラミングの方法で解決できる.

  • bottom-up方式で、連続プロトコルの最値を比較して保存し、数列を比較し続け、既存の連続プロトコルの最値と新しい連続プロトコルの値を比較することで問題を解決します.

  • 数列の数値は-1000以上、1000以下の整数です.すなわち、数列に負の数を含めることができる.したがって,各数字が正数であるか負数であるかによって,異なる処理を行うべきである.詳細は以下のコードにコメントしていますので、参考にしてください.

    • 正しいコード

    #include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int n;
    int arr[100001];
    int dp[100001];
    // dp[]에는 각 인덱스에서의 연속합을 더해 갖고 있는 역할을 한다.
    int res;
    // res 변수에는 가장 큰 연속값을 저장해 두고, 최종적으로 답을 출력하는 역할을 한다.
    
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>arr[i];
    }
    
    if (arr[1] >= 0) dp[1] = arr[1];
    else dp[1] = 0;
    res = arr[1];
    for(int i=2; i<=n; i++) {
        if (arr[i] >= 0) {
            // i번째 숫자가 양수인 경우, dp[]에 arr[i]를 더해준 것을 연속합으로 저장한다.
            dp[i] = dp[i-1] + arr[i];
            res = max(res, dp[i]);
        }
        else {
            // i번째 숫자가 음수인 경우, 두 가지 case가 가능하다.
            if (dp[i-1] + arr[i] >= 0) {
                // 기존 연속합 + 이번 음수 >= 0일 경우, 그대로 더해 연속합으로 저장해 둔다.
                dp[i] = dp[i-1] + arr[i];
                res = max(res, dp[i]);
            }
            else {
                // 기존 연속합 + 이번 음수 < 0일 경우, 이번 숫자를 더하면 연속합이 최대가 될 가능성은 없다.
                dp[i] = 0;
                res = max(res, arr[i]);
            }
        }
    }
    
    cout<<res<<endl;
    return 0;
}
    #First Project 1番目
    JOIN - SQL