MaxSubarray

1. 문제 * 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다. - 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다. 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 예를 들어, 아래와 같은 배열이 있다면, -2 -1 3 5 2 -5 0 2 이 배열의 최대부분배열의 합은 몇일까? 3+5+2 = 10 이다. 2. 해결방법 - 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다. - 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법 1) 완전탐색(브루트포스..