앞에서부터 더해온 값 중 최댓값과 다음을 더한 새로운 값을 비교하여 최댓값을 구해줍시다.
코드 (C++)
#include <iostream>
using namespace std;
int num[100001], dp[100001];
int main(int argc, const char *argv[]) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> num[i];
}
for (int i = 1; i <= N; i++) {
dp[i] = dp[i - 1] + num[i] > num[i] ? dp[i - 1] + num[i] : num[i];
}
int max = dp[1];
for (int i = 2; i <= N; i++) {
if (max < dp[i]) {
max = dp[i];
}
}
cout << max << endl;
return 0;
}
|