< 백준 BaekJoon : 1912번 연속합 > C++

<< 문제 >>

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

2차원 테이블로 각 조합들을 다 채워넣고 최대값을 찾으려니 당연히 시간초과가 뜨는 것을....

 

풀이 방법은 이렇습니다.

 

0~num 배열에 0번 부터 각 연속합을 저장하는데,

( 연속합 + i번째 값 , i번째 값 ) 이 중 더 큰 값을 저장합니다.

 

i번째 값보다 작아지면 연속합을 깨고 차라리 i번째부터 새로 시작하는 편이 좋기 때문입니다.

그러려면 연속합이 음수여야겠네요.

 

<< 코드 >>

#include <iostream>
using namespace std;


int arr[100000];
int val[100000];

int main() {

	int num;
	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> arr[i];
	}
		
	val[0] = arr[0];
	int maxVal = val[0];
	for (int i = 1; i < num; i++) {
		val[i] = max(val[i-1] + arr[i], arr[i]);
		if (val[i] > maxVal) {
			maxVal = val[i];
		}
	}

	cout << maxVal;
}

 

 

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1912.%E2%80%85%EC%97%B0%EC%86%8D%ED%95%A9