4097 수익

4097 수익 https://www.acmicpc.net/problem/4097

수익이 가장 많이 나는 구간의 수익을 구하는 문제이다.

two pointer문제인줄 알고 계속 시도 해봤는데 답이 안나왔다.

다음과 같은 입력이 있을 때 3+4-3-5 = -1이므로 이 구간은 더하지 않는것이 더 최적이다.

#include <cstdio> #include <algorithm> using namespace std; int N; int main() {     while (scanf("%d", &N), N != 0){         int ans = -987654321;         int sum = 0;         for (int n = 0;n < N;n++) {             int v;             scanf("%d", &v);             sum += v;             ans = max(ans, sum);             sum = max(sum, 0);         }         printf("%d\n", ans);     }     return 0; } Colored by Color Scripter

cs