[leetcode][53] Maximum Subarray

문제 : https://leetcode.com/problems/maximum-subarray/

---

문자열을 앞에서부터 더해간다.

더한 값이 양수라면 앞으로의 탐색 값에 더했을 때 더 큰 합을 기대할 수 있다.

하지만 음수라면 무슨 수를 더해도 더 작은 합이 나올 것이다.

따라서 더한 값이 음수가 나오면 부분합을 0으로 초기화시키고 다시 배열 값을 더해간다.

이렇게 구한 부분합들 중 최대값이 정답이 된다.

시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/157788123006e2e518e352129645b170