[BOJ/C+]13398回連続2

9056 ワード
dynamic programming DP boj cpp テキストリンク
Pythonで解読したコードをC++で再解読します.Pythonコードのように解釈しているので説明は省略する.
[BOJ/Python]13398回連続2

Code

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;

int n;
int arr[MAX];
int dp[MAX][2];
int answer=-999999999;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        dp[i][0]=arr[i];
        dp[i][1]=-999999999;
    }
}

void Solution(){
    for(int i=1; i<n; i++){
        dp[i][0]=max(dp[i-1][0]+arr[i], arr[i]);
        dp[i][1]=max(dp[i-1][0], dp[i-1][1]+arr[i]);
    }
    for(int i=0; i<n; i++){
        answer=max(answer, max(dp[i][0], dp[i][1]));
    }
    cout<<answer<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}
8月30日Velog
[アルゴリズム]Bubble Sort