[BOJ] 1912번 : 연속합

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int nums[100005];
int d[100005];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> nums[i]; 

	for (int i = 1; i <= n; i++) {
		d[i] = max(d[i - 1] + nums[i], nums[i]); 
	}
	cout << *max_element(d+1,d+n+1) << '\n';
}

 

3. solution 2:

// Authored by : Hot6Mania
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/1fb4beecefac47d7a7f45f97f3189806
#include <bits/stdc++.h>
using namespace std;

int n;
int a[100010];
int d[100010]; // d[i] : i번째 항으로 끝나는 연속합 중 최대

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  for(int i = 1; i <= n; ++i)
    d[i] = max(0, d[i-1]) + a[i];
  cout << *max_element(d + 1, d + n + 1);
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1912.cpp

basic-algo-lecture/0x10/solutions/1912.cpp at master · encrypted-def/basic-algo-lecture