[C++] 1912: 연속합

실버 Ⅱ

 

#include <iostream>
using namespace std;
int N;
int arr[100000];
int dp[100000];

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	dp[0] = arr[0];

	int ans = dp[0];
	for (int i = 1; i < N; i++) {
		if (dp[i - 1] > 0) dp[i] = arr[i] + dp[i - 1];
		else dp[i] = arr[i];
		if (dp[i] > ans) ans = dp[i];
	}
	printf("%d", ans);
}

 

투포인터로 첨에 해보려 했는데

배열의 원소에 마이너스가 있어서 안되는 것으로 추측...

사실 투포인터 원리를 제대로 다 이해 못한거 같기도 하고ㅋㅋ

아무튼 내 추측으로는 마이너스땜에 안되는거같음

 

문제 해설

포함하거나~~ 에서 포함당하는거는 dp[i-1] 인데 dp[i-1]이 나타내는건

수열 i-1 원소까지의 연속합 중 가장 큰 값이다.

그래서.. 그냥 dp[i-1]이 양수이기만 하면 그 값을 반영해서 넣어주면 된다

0일경우는 둘 중 어떤 액션을 취하든 의미 없기 때문에 if문/else문 중 암데나 넣어주면 됨