개요

백준1912(연속합)

• 입력
  첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

• 출력
  첫째 줄에 답을 출력한다.

접근방식

1. 백준10211(Maximum Subarray) 풀이 문제에서 조건의 최대값이 증가한 문제이다.

2. 따라서 해당 풀이에서 적어놓은 1번 방식으로 풀 시 시간초과가 나며,
   2번(반복문을 돌며 합을 갱신시키는 방식) 방식 아니면
   3번(점화식을 이용한 다이나믹 프로그래밍) 방식을 이용해야 한다.

2번 방식 코드

#include<iostream>
#include<algorithm>

using namespace std;
int inputArr[100'001];
bool isAllElemNeg = true;

void Input() {
	int N = 0, maxSum = -1'000'000,tmpSum=0,maxInt=-1001;
	
	cin >> N;
    //입력을 받으면서 동시에 모든 원소가 음수인지 체크 및 제일 큰 원소 저장하기
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
		if (inputArr[i] > 0) isAllElemNeg = false;
		maxInt = maxInt > inputArr[i] ? maxInt : inputArr[i];
	}
    
    //모든 원소가 음수값일 시
	if (isAllElemNeg) {
		//제일큰값이 답
		maxSum = maxInt;
	}
    //음수값이 아닐 시
	else
		for (int i = 0; i < N; i++) {
			tmpSum += inputArr[i];
			//음수가되면 0으로 초기화 
			if (tmpSum < 0) tmpSum = 0;
			//각 반복마다 maxSum 갱신해주기
			maxSum = max(tmpSum, maxSum);
		}
	cout << maxSum;
}



int main() {
	Input();
}

3번 방식 코드

#include<iostream>
#include<algorithm>

using namespace std;
int dp[100'002];
int N = 0, maxSum = -1'000'001;

void Input() {
	int inputInt=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> inputInt;
		//dp[i+1]에는 (i번째 dp값인 dp[i]+ i번째 입력값 )과 i번째 입력값을 비교해 더 큰값이 들어감,
		dp[i + 1] = max(dp[i] + inputInt, inputInt);
		//최대값 갱신
		maxSum = maxSum > dp[i + 1] ? maxSum : dp[i + 1];
	}
	cout << maxSum;
}



int main() {
	Input();
}

문풀후생

백준10211(Maximum Subarray) 문제보다는 최대값이 커져서 좀 어렵지만 10211문제때 이미 최대값이 커질때 대비한 풀이들로 풀어놔서 시간이 적게 걸렸다.