最大部分和問題

問題概要

n個の整数が与えられます。これらの整数から何個かを選んで総和をとったときの、総和の最大値を求めるプログラムを作成する。また、何も選ばない場合の総和は0とする

アプローチ

この問題は、ダイナミックプログラミングのアプローチを用いて解く。ダイナミックプログラミングは、複雑な問題をより簡単な部分問題に分割し、それらの結果を組み合わせて全体の問題を解く手法。

ここでは、dp[i] をi番目までの数から選んだ総和の最大値とする。このとき、次の状態 dp[i + 1] を次のように更新する：dp[i + 1] = max(dp[i], dp[i] + a[i])。これは、次の数 a[i] を選ぶか選ばないかのどちらが総和を最大にするかを比較する

コード

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int a[10010];
int dp[10010];

int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];

dp[0] = 0;
for (int i = 0; i < n; ++i) {
dp[i + 1] = max(dp[i], dp[i] + a[i]);
}

cout << dp[n] << endl;
}