LeetCode Day동적 프로그래밍 파트8

121. 주식을 사고 팔기에 가장 좋은 시기

가격[i]이 i번째 날 특정 주식의 가격인 배열 가격이 제공됩니다.

특정 주식을 매수할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택하여 수익을 극대화하고 싶습니다.

이 거래에서 얻을 수 있는 최대 이익을 반환하세요. 수익을 얻을 수 없으면 0을 반환하세요.

예 1:

입력: 가격 = [7,1,5,3,6,4]
출력: 5
설명: 2일차 매수(가격 = 1), 5일차 매도(가격 = 6), 이익 = 6-1 = 5.
판매하기 전에 구매해야 하기 때문에 2일차 구매와 1일차 판매는 허용되지 않습니다.
예시 2:

입력: 가격 = [7,6,4,3,1]
출력: 0
설명: 이 경우 거래가 이루어지지 않으며 최대 이익 = 0입니다.

제약사항:

1 0 원본페이지

방법 1, 그리디 알고리즘

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }

시간 O(n) 공간 O(1)

방법 2 동적 프로그래밍

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

시간 O(n) 공간 O(n)
동적 프로그래밍은 특정 문제에만 작동하지 않기 때문에 그리디 알고리즘보다 더 일반적입니다.

방법 2.1(공간 복잡도 개선)

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

여기서 dp[1]을 먼저 처리해야 한다는 점에 주의하세요. 업데이트된 dp[0] 대신 이전 dp[0]을 사용하기 때문입니다.

122. 주식을 사고 파는 가장 좋은 시기 II

price[i]가 i번째 날 특정 주식의 가격인 정수 배열 가격이 제공됩니다.

매일 주식을 매수 및/또는 매도하기로 결정할 수 있습니다. 귀하는 언제든지 주식을 최대 1주만 보유할 수 있습니다. 단, 구매 후 당일 바로 판매도 가능합니다.

당신이 달성할 수 있는 최대 수익을 찾아 돌려보세요.

예 1:

입력: 가격 = [7,1,5,3,6,4]
출력: 7
설명: 2일차 매수(가격 = 1), 3일차 매도(가격 = 5), 이익 = 5-1 = 4.
그런 다음 4일차에 매수(가격 = 3)하고 5일차에 매도(가격 = 6), 이익 = 6-3 = 3.
총 이익은 4 + 3 = 7입니다.
예시 2:

입력: 가격 = [1,2,3,4,5]
출력: 4
설명: 1일차 매수(가격 = 1), 5일차 매도(가격 = 5), 이익 = 5-1 = 4.
총 수익은 4입니다.
예시 3:

입력: 가격 = [7,6,4,3,1]
출력: 0
설명: 긍정적인 수익을 낼 수 있는 방법이 없으므로 최대 수익 0을 달성하기 위해 주식을 구매하지 않습니다.

제약사항:

1 <= 가격.길이 <= 3 * 10…4
0 <= 가격[i] <= 10…4

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

롤링 어레이 방식

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. 주식을 사고팔기에 가장 좋은 시기 III

가격[i]이 i번째 날 특정 주식의 가격인 배열 가격이 제공됩니다.

당신이 달성할 수 있는 최대 수익을 찾아보세요. 최대 2개의 거래를 완료할 수 있습니다.

참고: 동시에 여러 거래에 참여할 수 없습니다(즉, 다시 구매하기 전에 주식을 판매해야 합니다).

예 1:

입력: 가격 = [3,3,5,0,0,3,1,4]
출력: 6
설명: 4일차 매수(가격 = 0), 6일차 매도(가격 = 3), 이익 = 3-0 = 3.
그런 다음 7일차에 매수(가격 = 1)하고 8일차에 매도(가격 = 4), 이익 = 4-1 = 3.
예시 2:

입력: 가격 = [1,2,3,4,5]
출력: 4
설명: 1일차 매수(가격 = 1), 5일차 매도(가격 = 5), 이익 = 5-1 = 4.
동시에 여러 거래를 진행하므로 1일차에 구매하고 2일차에 구매하고 나중에 판매할 수는 없습니다. 팔아야 재구매가 가능합니다.
예시 3:

입력: 가격 = [7,6,4,3,1]
출력: 0
설명: 이 경우 거래가 이루어지지 않습니다. 즉, 최대 이익 = 0입니다.

제약사항:

1 0

    public int maxProfit(int[] prices) {
        int transactions = 2;
        int[][] dp = new int[prices.length][transactions*2+1];
        for(int i=1; i<=transactions; i++){
            dp[0][i*2-1] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

위 내용은 LeetCode Day동적 프로그래밍 파트8의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!