[Algorithm/Swift] Codility / MaxProfit

 

문제

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

풀이

주식에서 언제 사고 언제 팔았을때 가장 큰 이익을 보는지 구하는 문제입니다.

6개의 요소의 차를 하나씩 해보면 답이 나오지만 그러면 BruteForce(무차별, 전체탐색)으로 O(N²) 느리게 답을 구하게 됩니다.

따라서 Dynamic Programming 적용한 Kadane’s Algorithm O(N) 을 사용해서 구해봅시다.

각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값

Code O(N)

public func solution(_ A : inout [Int]) -> Int {
    
    
	var maxProfit = 0
	var cheapestPrice = A.first ?? 0
	for price in A {
		cheapestPrice = min(cheapestPrice, price)
		maxProfit = max(maxProfit, price - cheapestPrice)
	}
	
	return maxProfit
}