* 문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

* 풀이
수열의 원소중 연속된 숫자를 선택해 가장 큰 합을 구하기 위해서 동적계획법(Dynamic Programming)을 사용합니다. 첫번째 원소부터 별도의 배열(dp배열)에 수열값과 그전까지 합한 값 중 큰값을 저장합니다. 그중 최댓값을 구하면 정답입니다. 이해가 안가시면 아래 코드를 주석과 함께 한 줄 씩 해석해 보시기 바랍니다.

* 소스코드

#include <iostream> 
#define MAX(a,b) ((a) > (b) ? (a) : (b)) 
using namespace std; 

int main(){ 
     int input_value = 0; 
     cin >> input_value; 
     int *data = new int[input_value]; 
     int *dp = new int[input_value];  // 배열 동적 할당
     int max = -1001; // max는 입력 값 중 가장 작은값보다 작은값

     for (int i = 0; i < input_value; i++)  
          cin >> data[i]; // 데이터 입력

     dp[0] = data[0]; // 첫번째 원소는 그대로 대입(그 자체로 최대값)

     for (int i = 1; i < input_value; i++) 
          dp[i] = MAX(data[i], data[i] + dp[i - 1]); 
          // dp배열에 원소 값과 그전 dp값을 합한 값 중 큰 값 대입

     for (int i = 0; i < input_value; i++) 
          if (max < dp[i]) max = dp[i]; // 최댓값 검색

     cout << max; 

     delete[] dp; 
     delete[] data; // 배열 동적 할당 메모리 해제

     return 0; 
}

질문 및 오류사항은 댓글로 달아주세요.


'자료구조, 알고리즘' 카테고리의 다른 글

정렬 알고리즘 종류  (0) 2018.09.12
검색 알고리즘 종류  (2) 2018.09.11
자료구조 그래프(Graph)  (1) 2018.09.06
자료구조 힙(Heap)  (0) 2018.09.05
자료구조 이진 탐색 트리(Binary Search Tree)  (0) 2018.09.01
자료구조 트리(Tree)  (0) 2018.08.30
[자료구조] 큐 QUEUE  (0) 2018.08.19
[자료구조] 스택 STACK  (0) 2018.08.19

to Top