매일 LeetCode 풀기 | Maximum Subarray

 

Given an integer array nums, find the 
subarray
 
with the largest sum, and return
 
its sum
.

 
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
 
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104

 

아예 접근방식을 모르겠어서 못풀었다. 

 

배운 코드 

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {

        guard !nums.isEmpty else { return 0 }

        var currentSum = nums[0]
        var maxSum = nums[0]

        for i in 1..<nums.count {
            currentSum = max(nums[i], currentSum + nums[i])
            maxSum = max(currentSum, maxSum)
        }

        return maxSum
    }
}

접근 방식 
1. 현재까지의 합을 나타내는, currentSum 그리고 maxSum을 각각 nums[0]으로 초기화 한다. 
2. 배열 반복문을 돌린다. 
3. currentSum은 nums[i] 그리고 currentSum+nums[i] 중에 더 큰 값을 저장한다. 
4. maxSum은 currentSum과 maxSum 중에 더 큰 값을 저장한다. 
5. 최종적으로 maxSum 값을 return 한다. 

 

---

 

카데인 알고리즘 

 

• 문제 정의:
  • 정수 배열에서 연속된 부분 배열 중 합이 최대인 것을 찾는 문제를 해결합니다.
• 핵심 아이디어:
  • 배열을 순회하면서, 각 위치에서 끝나는 최대 부분 배열의 합을 계산합니다.
  • 이전까지의 합이 음수라면 버리고 새로 시작하는 것이 유리합니다.
• 두 가지 주요 변수:
  • currentSum: 현재 위치까지의 최대 부분 배열 합
  • maxSum: 전체 배열에서 발견된 최대 부분 배열 합
• 동적 프로그래밍 접근:
  • 각 단계의 결과(현재까지의 최대 합)를 이용해 다음 단계의 결과를 계산합니다.
• 최적 부분 구조:
  • 전체 문제의 최적해는 부분 문제의 최적해로 구성됩니다.

 

배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

단계   현재 요소   currentSum   maxSum   설명
1      -2          -2           -2      시작
2       1           1            1      1 > -2 + 1, 새로 시작
3      -3          -2            1      1 + (-3) = -2
4       4           4            4      4 > -2 + 4, 새로 시작
5      -1           3            4      4 + (-1) = 3
6       2           5            5      3 + 2 = 5
7       1           6            6      5 + 1 = 6
8      -5           1            6      6 + (-5) = 1
9       4           5            6      1 + 4 = 5

최종 결과: maxSum = 6
최대 부분 배열: [4, -1, 2, 1]