https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
얘는 살짝 만 생각하면 답이나오는 문제 였다. 문제 푸는 방법이 퍼뜩퍼뜩 났으면 좋겠는데 아직 수련이 부족해서 시간이 오래 걸린다.
이 문제는 간단하다 내이전에 나온 최댓값과 나를 더한값과 나 혼자 값중에 더큰애를 선택해주면 되는 문제였다.
그 이유는 어찌됬든 더하는 수가 양수라면 값은 증가하기 때문이다
10
10 -4 3 1 5 6 -35 12 21 -1즉 이런식으로 입력이 주어지면
dp[1]은 -4와 6중에 선택한다
dp[2]는 3과 9중에 선택한다
dp[3]은 10과 1중에 선택한다
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | 12 | 33 | 32 |
이런식으로 dp값이 바뀐다 즉 점화식은
max(dp[i-1]+arr[i],arr[i])값이 된다
#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];
int max(int x,int y) {
return x > y ? x:y;
}
int main() {
int inputnum;
int maxnum;
cin >> inputnum;
for (int i = 0; i < inputnum; i++) {
cin >> arr[i];
}
dp[0]=arr[0];
maxnum = dp[0];
for (int i = 1; i < inputnum; i++) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
}
for (int i = 0; i < inputnum; i++) {
if (dp[i] > maxnum) {
maxnum = dp[i];
}
}
cout << maxnum;
}