이러한 것은 다이나믹 프로그래밍이라는 것과 같이 동적으로 수행하면서 최대부분을 갱신하면서 찾는 것이다. 물론 for문 2번 돌아서 가능하지만.. n^2은 써서는 안되는 최악의 시간 복잡도다. 다른 방법을 찾아보자 우선 정답코드를 보고난 다음 설명을 해보자 int MaxSubArray(int a[], int length) { int maxSoFar = 0, maxEndingHere = 0; // 1 for(int i = 0; i 이것은 부분배열합의 특성때문이다. 우선 문제부터 정의하자 부분배열합이란 무엇인가하니? 배열의 원소 중에서 임의의 원소 k번째부터 k + x까지의 합을 부분 배열이라 하고 해당 원소들의 합을 부분배열 합이라고 한다. 그렇다면 최대한의 합이 나오려면 가장 큰 부분을 고르면 되겠네? 맞..