BOJ/1912

연속합

**아래 코드는 정답이 아닙니다**

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <algorithm>


int main() {

	int x;
	scanf("%d", &x);
	
	int arr[100009] = {0,};

	for (int i = 1; i <= x; i++) {
		scanf("%d", &arr[i]);
	}
	int real_big = -100000000;
	for (int i = 1; i <= x; i++) { // 합의 개수
		int mem = -100000000;
		int sum = 0;
		for (int j = i; j <= x; j++) {
			sum += arr[j];
			if (sum > mem) {
				mem = sum;
			}
		}
		if (mem > real_big) {
			real_big = mem;
		}
	}

	printf("%d", real_big);
	
	
	return 0;
}​

단순히 모든 연속합을 구하여 가장 큰 것을 고르는 방법으로는 시간이 오래 소요되어(O(n^2)) 정답으로 통과되지 않는다.

 

카데인 알고리즘

전체 배열에서 부분합을 구하는 방법.

• 새 배열을 만들고 처음 요소부터 수열의 합을 구해 입력한다.
• (현재 수 + 이전 요소들까지의 합) < 현재 수 이면 합을 초기화하고 다시 수열의 합을 구해 배열에 저장.
• 만들어진 배열 중 가장 큰 값이 부분합의 최대이다.
•  

**아래 코드가 정답**

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <algorithm>


int main() {

	//카데인 알고리즘//

	int x;
	scanf("%d", &x);
	
	int arr[100009] = { 0, };

	for (int i = 1; i <= x; i++) {
		scanf("%d", &arr[i]);
	}

	int ss[100009] = { 0, };//계산되는 수열을 저장할 배열
	
	ss[1] = arr[1];
	int sum = arr[1];
	
	for (int i = 2; i <= x; i++) {
		if (ss[i - 1] + arr[i] < arr[i]) { //이번 숫자와 이전 숫자들끼리의 합이 이번 숫자보다 작으면 초기화
			sum = 0;
		}
		sum += arr[i]; //처음/초기화 이후부터 현재 수열까지의 합
		ss[i] = sum; // sum을 ss배열에 추가
	}

	/* ss출력
	for (int i = 1; i <= x; i++) { //ss배열 중 가장 큰 값이 답.
		printf("%d", ss[i]);
	}
	*/

	int big = -100000000;
	for (int i = 1; i <= x; i++) { //ss배열 중 가장 큰 값이 답.
		if (ss[i] > big) {
			big = ss[i];
		}
	}
	
	printf("%d\n", big);
	
	return 0;
}​