[욕심 알고리즘] [동적 기획] 주식 매매 의 적기 II

1867 단어 알고리즘 문제
문제 설명
배열 을 지정 합 니 다. i 하나의 요 소 는 주어진 주식 제 이다. i 하늘의 가격.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 가능 한 한 더 많은 거래 를 완성 할 수 있다.
주의: 당신 은 여러 가지 거래 에 동시에 참여 할 수 없습니다.
예시 1:
  : [7,1,5,3,6,4]
  : 7
  :    2  (     = 1)     ,   3  (     = 5)     ,            = 5-1 = 4 。
       ,   4  (     = 3)     ,   5  (     = 6)     ,            = 6-3 = 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:
class Solution {
    public int maxProfit(int[] prices) {
        if(null == prices || prices.length == 0){
            return 0;
        }

        int max = 0;
        for(int i = 1; i < prices.length; i++){
            max += Math.max(prices[i] - prices[i - 1], 0);
        }

        return max;
    }
}

 
해법 2:
class Solution {
    public static int maxProfit(int[] prices) {
        if(null == prices || prices.length <= 1){
            return 0;
        }

        int[][] dp = new int[prices.length][prices.length];
        for(int i = 0; i < prices.length; i++){
            for(int j = i; j < prices.length; j++){
                int tmp = Math.max(j > 0 ? dp[i][j - 1] : 0, i > 0 ? dp[i - 1][j] : 0);
                tmp = Math.max(tmp, prices[j] - prices[i] + (i > 0 ? dp[i - 1][i - 1] : 0));

                dp[i][j] = tmp;
            }
        }

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

좋은 웹페이지 즐겨찾기