[알고리즘] 최대 Subarray 찾기

아래와 같은 배열(집합)이 있다.

1

-3

2

4

-1

5

-3

 

이 배열의 부분집합중에, 합이 가장 큰 것은 무엇인가?

답은 2, 4, -1, 5 를 더한 10이다.

 

이것을 어떻게 빨리 구할 수 있을까?

 

---------

 

내가 생각한 방법은 이렇다.

 - 양수로 시작, 양수로 끝.

 

목록을 만들어보자면 이와 같다.

•  1, -3, 2, 4
•  2, 4, -1, 5
• 4, -1, 5
• 5

하지만 모두가 음수이거나, 양수이면?

음수일 때 : 최솟값 1개가 정답.

양수일 때 : 모든값을 더한것이 정답.

 

알고리즘 시간복잡도는 O(N^2)일 것이다.

 

---------

 

제시하는 알고리즘은 다음과 같다.

 

Count 변수가 있다. Count 변수는 배열을 더해간다. 만약 Count 변수가 음수가 된다면, 0으로 초기화 한다.

 

이렇게 끝까지 갔을 때 나온 값이 정답이다.

 

하지만

 

아래와 같은 케이스에서는 동작하지 않았다.

1

-9

7

2

3

-8

2

5

 

답은 7+2+3 으로 12가 되야하는데,

위의 알고리즘을 따르면 11이 된다.

 

좀 더 알아봐야겠다.