본문 바로가기
[C++] 알고리즘 교육/15. 분할정복법

[알고리즘 15.1.1] 분할정복법 - 연속부분최대합

by 안산학생 2019. 4. 24.

문제


N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

 

입력


첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다.

 

출력


연속된 부분을 선택하였을 때의 최댓값을 출력한다.

 

예제 입력

8 2 3 -5 8 -3 4 2 -9

예제 출력

11

 

예제 입력

5 -1 -2 3 -2 4

예제 출력

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
 
using namespace std;
 
const int MAX = 1000005;
int n;
int arr[MAX];
int t[MAX];
 
int main(){
  
  cin>>n;
  
  for(int i=0; i<n; i++cin>>arr[i];
  
  t[0= arr[0];
  
  for(int i=1; i<n; i++){
    if(t[i-1]+arr[i]>arr[i]){
      t[i] = t[i-1]+arr[i];
    }else{
      t[i] = arr[i];
    }
  }
  
  int temp = -987987987;
  for(int i=0; i<n; i++){
    if(t[i]>temp){
      temp= t[i];
    }
  }
  
  cout<<temp<<endl;
  
  return 0;
}
 

댓글