LeetCode 121. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

 

문제를 보고 이건 마지막인덱스에서 최고값을 찾아서 거꾸로 들어가면 되지 않을까? 라는 생각이 먼저 들었다.

 

제일 높은 가격을 갖고 앞인덱스로 이동하면서 각각 판매이익을 계산하는 방법으로 진행해봤다.

 

더 큰 값이 나온다면 현재 지금까지 제일 이익이 높았던 가격에 판매를 하고 최고값을 다시 갱신 후 앞으로 이동한다.

 

prices = [7,1,5,3,6,4]

start = len(prices)-1


result = 0
max_value = prices[start]
max_profit =0
temp_profit = 0
for i in range(start,-1,-1):
    if prices[i] < max_value:
        if max_value - prices[i] > max_profit:
            max_profit = max_value- prices[i]
    elif prices[i] > max_value:
        result+=max_profit
        max_profit=0
        max_value= prices[i]

result+= max_profit

print(result)

일단 답은 틀렸다.. 중간에 최고값으로만 비교해서 그런거같다 중간 중간에 temp를 통해서 중간에 팔리는 가격도 계산해줘서 넣어주면 풀릴거같으나 시간이 부족해서 보류!