[LeetCode] 53번 - Maximum Subarray [Swift]

문제 링크

Maximum Subarray - LeetCode

문제 

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [0] Output: 0

Example 4:

Input: nums = [-1] Output: -1

Example 5:

Input: nums = [-100000] Output: -100000

문제 풀이

이 문제는 주어진 배열에서 연속된 값들의 합 중 최대값을 구하는 문제입니다.

 

처음에 임시값, 정답값을 각각 0으로 만들어줍니다.

배열의 첫 숫자 부터 임시값에 계속 더하면서 값이 양수라면 정답값과 비교하여 더 큰 값을 정답값으로 설정하고, 만약 임시값이 음수라면 이는 양수가 하나라도 존재하는 배열에서는 반드시 최댓값이 아니므로 임시값을 0으로 다시 설정합니다.

이렇게 배열의 모든 값을 확인한 뒤엔 정답값에는 정답이 있거나 0이 있는데요, 만약 0이 있다면 주어진 배열의 모든 값이 음수라는 뜻이므로 주어진 배열의 최대값이 정답!입니다.

 

물론 모든 값이 음수일경우가 존재할 수 있고 이 때는 주어진 배열의 최대값이 정답입니다!

소스 코드

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var result: Int = 0
        var temp: Int = 0
        for i in 0..<nums.count {
            temp += nums[i]
            if temp < 0 {
                temp = 0
            } else {
                if temp > result {
                    result = temp
                }
            }
        }
        if result == 0 {
            return nums.max()!
        }
        
        return result
    }
}