이러한 것은 다이나믹 프로그래밍이라는 것과 같이
동적으로 수행하면서 최대부분을 갱신하면서 찾는 것이다.
물론 for문 2번 돌아서 가능하지만.. n^2은 써서는 안되는 최악의 시간 복잡도다.
다른 방법을 찾아보자
우선 정답코드를 보고난 다음 설명을 해보자
int MaxSubArray(int a[], int length)
{
int maxSoFar = 0, maxEndingHere = 0; // 1
for(int i = 0; i<size; i++){
maxEndingHere = maxEnding + a[i]; // 2
if(maxEndingHere < 0){ // 3
maxEndingHere = 0;
}
if(maxSoFar < maxEndingHere){ //4
maxSoFar = maxEndingHere;
}
}
return maxSoFar;
}
4가지 부분으로 나누어 보았다
필요한 것은
시간을 줄이기 위해서 동작하면서 최댓값을 갱신하는 것이다.
**이전의 task에서는 정답이 나올 수 없다는 것을 알고 쓰는 것이다.
다시 말하면 순차적으로 n개에 대해서 접근을 하지만 이전에 검색한 것들이
앞으로 나올 것들에게 영향을 주지 않는다는 것이다.
쉽게 말해서 한 번 검색한 것은 다시 검색하지 않는다.
-> 이것은 부분배열합의 특성때문이다.
우선 문제부터 정의하자
부분배열합이란 무엇인가하니?
배열의 원소 중에서
임의의 원소 k번째부터 k + x까지의 합을 부분 배열이라 하고 해당 원소들의 합을 부분배열 합이라고 한다.
그렇다면 최대한의 합이 나오려면 가장 큰 부분을 고르면 되겠네?
맞다. 하지만 큰 수 [10,11,12] 가 있더라도 앞에 [3,2,4,3,3,5]가 더 클 수 있다.
즉, 큰 부분만 고려할 것이 아니라 어디부터 더해야 하는가? 가 중요하다.
더군다나 주어진 문제의 범위에서는 음수도 출현가능하다.
그래서 한 번 풀어보자
1. 동적으로 찾은 최댓값을 저장하는 값, 현재 내가 조사하고 있는 부분배열의 합을 저장한다.
2. 내가 i번째를 조사했을 때, 다시 말해서 i번째 까지의 합을 maxEndingHere에 저장한다.
3. 내가 i번째를 조사했을 때, 내가 조사하고 있는 부분배열의 합이 음수가 된다면
-> 해당 부분배열의 합은 버려야한다
뒤에서 더 커질 가능성이 있으니까? 버리면 안되는 것 아니에요??
라고 할 수 있다.
뒤에서 양수가나오면 그 양수부터 다시 부분배열합을 구하는 것이 합을 더 키우는 방법이다.
예를 들어
3,4,5,-15,11 ...이라 치면
3 -> 7 -> 12 -> -3 -> 8 ....
이런 식일 텐데..?
분명 11을 만나서 부분배열 합이 8이 된 것은 맞지만
-3을 굳이 합쳐서 11부터 시작할 것은 8로 시작한 것이다.
이전의 부분배열합이 음수가 된다면 다음에 나올 것과 상관없이 버리는 것이 더 이득이라는 말이다.
쉽게 말해서 음수가 나왔는데 뭐하러 해당 음수를 더하느냐? 이 말이다.
4. 만약 내가 조사하고있는 부분배열의 합이 지금 내가 가지고 있는 최댓값보다 크면 갱신해준다.
마지막으로 다 조사한 뒤 최댓값을 반환한다.