[Codility] 9. Maximum slice problem (MaxProfit, MaxSliceSum)

Maximum slice problem

각 위치에 대해 해당 위치에서 끝나는 가장 큰 합을 계산합니다. 만약 위치 i에서 끝나는 슬라이스의 최대 합이 max_ending과 같다고 가정하면 위치 i+1에서 끝나는 최대 슬라이스는 max(0, max_ending+ $a_{i+1}$ )와 같습니다.

#O(n)
def golden_max_slice(A):
    max_ending=max_slice=0
    for a in A:
        max_ending=max(0,max_ending+a)
        # +가 된다면 max_ending에 계속 쌓아가기
        # -라면 0부터 다시 시작하기

        # max_slice 찾기
        max_slice = max(max_slice, max_ending)

    return max_slice

9.1 MaxProfit

Task description

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q]. Write a func that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

이것은 N일 연속된 주식 일별 가격을 포함합니다. 만약 P일에 하나의 주식을 사고 Q일에 팔았는데, 여기서 0 ≤ P ≤ Q < N이면, 그러한 거래의 이익은 A[Q] - A[P]와 같으며, A[Q] ≥ A[P]가 아니면, 그 거래는 A[P] - A[Q]의 손실을 가져옵니다. N일 연속된 주식 일별 가격을 포함하는 N개의 정수로 구성된 배열 A가 주어지면, 이 기간 동안 한 거래에서 최대 가능한 이익을 반환하는 함수를 작성하십시오. 만약 이익을 얻을 수 없다면, 함수는 0을 반환해야 합니다.

def solution(A):
   buy = 200000
   profit = 0

   for a in A:
      buy = min(a, buy)
      profit = max(profit, a - buy) # a가 순차적으로 돌아서 buy가 a이전 주식가격의 최저가격임

   return profit

9.2 MaxSliceSum

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q]. Write a func that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

0 ≤ P ≤ Q < N인 정수의 쌍 (P, Q)을 배열 A의 조각이라고 합니다. 조각의 합 (P, Q)은 A[P] + A[P+1] + ... + A[Q]의 합입니다. N개의 정수로 구성된 배열 A가 주어지면 A의 어떤 조각의 최대 합을 반환하는 함수를 작성하십시오.

def solution(A):
	max_ending = 0
	max_slice = A[0]
	for a in A:
		max_ending = max(a, max_ending + a) # a부터 reset(0 아님!)
		max_slice = max(max_slice, max_ending)
	return max_slice