본문 바로가기
알고리즘 문제/Leetcode

[leetcode][53] Maximum Subarray

by 햄과함께 2018. 11. 4.
320x100

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




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

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

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

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

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


시간복잡도는 O(N).




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

320x100

댓글