Maximum Subarray

문제

https://leetcode.com/problems/maximum-subarray/description/

입력

1 <= nums.length <= 105
-10^4 <= nums[i] <= 10^4

결과

ans: Int = 가장 큰 부분수열의 합

해석

누적합이 현재 값보다 작으면, 이전 누적합을 버리고 그렇지 않으면 계속 누적한다.

이 때 누적할 때마다 이전의 최대값과 계속 비교해서 저장한다.

코드

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        let len = nums.count 
        var currentMax = nums[0] // 누적합
        var ans = nums[0] // 최종 결과 
        
        for i in 1..<len {
            currentMax = max(nums[i], currentMax+nums[i]) // 누적합이 더 작으면 현재껄로 새로 시작
            ans = max(currentMax, ans) // 최대값 갱신
        }
        return ans
    }
}