Maximum Subarray
[Leetcode :: Maximum Subarray]
정수 배열 nums를 지정하면 합계가 가장 큰 연속적인 하위 배열(최소 1개를 포함)을 찾아 합계를 반환하십시오.
접근 방법
Brute Force
주어지는 배열은 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]로 구성돼 있다.
문제를 보면 하나의 배열안에 하위 배열들의 합을 구하는 것이라 단순하게 생각해도 반복문 2개로 풀 수 있을 것이다. A[0]부터 시작되는 하위 배열들부터 A[1]~A[N-1]로 시작하는 하위 배열들의 합 중에서 제일 큰 걸 고르면 되는데 이렇게 작성을 하면 시간 복잡도는 O(n^2^)으로 너무 느려진다.
