1912번 연속합

문제링크 : www.acmicpc.net/problem/1912

1912번: 연속합

---

---

<알고리즘>

 1) 입력받은 수를 넣는 배열 number과는 별도의 숫자들의 합을 넣을 배열 dq를 생성

 2) for문을 통해 dq의 i번째 값으로 number[i]와 dq[i-1]+number[i]중 더 큰값을 삽입

    여기서, dq[i-1]과 number[i]를 더하는 값은 이제까지 제일 큰 값에 지금 고려하는 값을 넣은 경우이고,

             그냥 number[i]는 이제까지의 값은 버리고(지금 값을 더 작게 만드는 값이기에) 새값을 고려하는 경우이다.

 3) dq를 만듦과 함께 가장 큰 값을 찾는 max함수 이용하기

       dq를 다 만든 후에 해도 되지만, 반복문을 줄이기 위해서 함께 하는 것이 좋다.

 

 

 

<표로 보는 풀이>

 

1) number과 dq 생성(dq와 max의 첫 값은 number[0]값으로 입력)

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10
max	10

 

2) dq[1] = number[1]과 dq[0]+number[1] 중 큰 값, max = dq[0]과 dq[1]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6
max	10	10

 

3) dq[2] = number[2]과 dq[1]+number[2] 중 큰 값, max = dq[1]과 dq[2]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9
max	10	10	10

 

4) dq[3] = number[3]과 dq[2]+number[3] 중 큰 값, max = dq[2]과 dq[3]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10
max	10	10	10	10

 

5) dq[4] = number[4]과 dq[3]+number[4] 중 큰 값, max = dq[3]과 dq[4]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15
max	10	10	10	10	15

 

6) dq[5] = number[5]과 dq[4]+number[5] 중 큰 값, max = dq[4]과 dq[5]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15	21
max	10	10	10	10	15	21

 

7) dq[6] = number[6]과 dq[5]+number[6] 중 큰 값, max = dq[5]과 dq[6]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15	21	-14
max	10	10	10	10	15	21	21

 

8) dq[7] = number[7]과 dq[6]+number[7] 중 큰 값, max = dq[6]과 dq[7]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15	21	-14	12
max	10	10	10	10	15	21	21	21

 

9) dq[8] = number[8]과 dq[7]+number[8] 중 큰 값, max = dq[7]과 dq[8]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15	21	-14	12	33
max	10	10	10	10	15	21	21	21	33

 

10) dq[9] = number[9]과 dq[8]+number[9] 중 큰 값, max = dq[8]과 dq[9]중 큰 값 

number	10	-4	3	1	5	6	-35	12	21	-1
dq	10	6	9	10	15	21	-14	12	33	32
max	10	10	10	10	15	21	21	21	33	33

 

 

 

메모리 : 2676KB    시간 : 28ms

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	cin >> N;

	int number[100001];
	int dq[100001];
	int a = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		number[i] = a;
	}

	dq[0] = number[0];
	int temp = dq[0];
	for (int i = 1; i < N; i++) {
		dq[i] = max(number[i], number[i] + dq[i - 1]);
		temp = max(temp, dq[i]);
	}
	cout << temp;
}

 

 

 

+) 실패한 코드

  why? 음수로만 이루어진 수열, 혹은 시작이 음수인 수열의 경우 0이 자꾸 삽입됨.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int N = 0;
	cin >> N;

	vector<int> number;
	int a = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		number.push_back(a);
	}

	vector<int> firstadd;
	vector<int> addMax;
	int sum = 0;
	for (int i = 0; i < N; i++) {
		if (number[i] >= 0) sum += number[i];
		else {
			firstadd.push_back(sum);
			addMax.push_back(sum);
			firstadd.push_back(number[i]);
			sum = 0;
		}
	}

	int start = 0;
	int index = 0;
	if (firstadd[0] >= 0 || firstadd.size() == 1) { start = firstadd[0]; }
	else {
		start = firstadd[1];
		index = 1;
	}
	while(index<firstadd.size()){
		if (index + 2 < firstadd.size()) {
			if (abs(firstadd[index + 1]) <= abs(firstadd[index + 2])) {
				start += (firstadd[index + 1] + firstadd[index + 2]);
				index += 2;
			}
			else {
				addMax.push_back(start);
				start = firstadd[index + 2];
				index += 2;
			}
		}
		else {
			break;
		}
	}

	int maximum = -1001;
	for (unsigned int i = 0; i < addMax.size(); i++) {
		maximum = max(maximum, addMax[i]);
	}
	cout << maximum << "\n";
	return 0;
}