1912年

まず入力した数字を最初から1つずつ進めていきます.
しかし、これまで以上に増やしたい数は多い.
もっと大きいと.
今までやってきたことをすべて放棄する.
加算する数から、もう1つずつ加算すれば、問題を解決できます.
説明が難しすぎて、例を使うのは簡単です.
問題テストケース1
10
10 -4 3 1 5 6 -35 12 21 -1
累積後の値はdp[size]、最大結果値はresultである.
プラス10.dp[0] = 10, result = 10
dp[0]プラス-4の値>-4なので=>を加算dp[1] = 6, result = 10
dp[1]プラス3の値>3なので=>を加算dp[2] = 9, result = 10
...
(...に-35を加える)=>dp[6]=-14,result=10
...
dp[6]に12の値<12を加え、dpを12に更新する.
=> dp[7] = 12, result = 12
dp[7]プラス21の値>21なのでプラス21.
=> dp[8] =33, result = 33
dp[8]プラス-1の値>-1なのでプラス-1.
=> dp[9] = 32, result = 33
したがって、正解はresult=33です.

ソースコード

非常に簡単に実現できます.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> sequence(n);
	vector<int> dp(n);

	for (int i = 0; i < n; i++) 
		cin >> sequence[i];
	
	int result = sequence[0];
	dp[0] = sequence[0];

	for (int i = 1; i < n; i++) {

		dp[i] = max(dp[i - 1] + sequence[i], sequence[i]);
		result = max(result, dp[i]);
	}

	cout << result;

}