Maximum Subaray(白駿10211号)

link : https://www.acmicpc.net/problem/10211
これは動的計画と暴力アルゴリズムを運用する問題である.
まず問題を見て,nの大きさの配列の中で要素の和の最大の部分数列を探す.
最初は、2つのポインタで近づき、値の和の中で最大の値を答えにしたいと思っていました.
問題ではおそらく要求の時間を満たすことができないので,別の方法を模索した.
結果は動的プログラミングを適用した.
まず、配列の値を含む配列を作成し、dp(Dynamic Programming)の値を含む配列を作成します.
for文を1から順に配列の値を比較します.
dpの値を比較します.

dp[1] = max(dp[0] + arr[1], arr[1]);
dp[2] = max(dp[1] + arr[2], arr[2]);
.
.
.

価格が-9999999999855なら.
ではdp[1]には-999が含まれている.
dp[2]は、-9999+998および998の大きな値を格納する.
998の方が大きいので998をMaximum Subarayに変更
そして、dp[3]は、998+5および5の大きな値998+5=1003を記憶する.
Maximum Subarayの値は1003です.
ソース:

#include <iostream>
using namespace std;

int dp[1001] = {0, };
int arr[1001] = {0, };


int main() {

	ios_base::sync_with_stdio(NULL);
	cin.tie();
	cout.tie();

	int t, n;
	cin >> t;

	while (t--) {
		cin >> n;
		int answer = -999999999;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			dp[i] = max(dp[i-1] + arr[i], arr[i]);
			answer = max(answer, dp[i]);
		}
		cout << answer << "\n";
	}
}