LintCode: 주식 을 사 는 가장 좋 은 시기 시리즈

LintCode 149：

       ，   i             i    。              (  ,      ),             。

분석: 한 번 만 매매 할 수 있 기 때문에 가격 이 가장 낮은 매입, 가격 이 가장 높 은 판 매 를 선택해 야 한다. 변수 로 가장 작은 매입 치 를 보존 하고 현재 판매 소득 의 이윤 을 얻어 현재 최대 이윤 에 비해 비교적 큰 것 을 선택해 야 한다.

public int maxProfit1(int[] prices) {
        int maxProfit=Integer.MIN_VALUE;
        int minbuy=Integer.MAX_VALUE;
        int len=prices.length;
        if(len==0)  return 0;
        for(int i=0;i

LintCode 150：

       ，   i             i    。              。            (      )。  ,           (             )。

분석: 여러 번 매매 할 수 있 고 배열 을 옮 겨 다 니 며 배열 의 앞 뒤 두 숫자 간 의 차 이 를 계산 할 수 있 습 니 다. 만약 에 0 보다 크 면 profit 에 누적 되 어 한 번 의 매매 로 얻 은 이윤 을 나타 내 고 마지막 에 총 이윤 으로 돌아 갑 니 다.

public int maxProfitII(int[] prices) {
        // write your code here
        if(prices==null || prices.length==0)    return 0;
        int diff=0;
        int profit=0;
        for(int i=0;i0){
                profit+=diff;
            }
        }
        return profit;
    }

LintCode 151：
묘사 하 다.
만약 에 배열 이 있다 고 가정 하면 그의 i 번 째 요 소 는 주어진 주식 이 i 일 째 가격 이다.알고리즘 을 설계 하여 가장 큰 이윤 을 찾다.너 는 최대 두 건의 거래 를 완성 할 수 있다.
분석: 각각 이전 과 이후 에 앞으로 옮 겨 다 니 며 각각 dp 배열 로 i 일 에 판 매 된 최대 이윤 과 i 일 에 산 최대 이윤 을 저장 하고 마지막 으로 두 dp 배열 을 옮 겨 다 니 며 이 를 더 해 최대 이윤 으로 돌아 가면 된다.

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if(prices==null||prices.length<=1)  return 0;
        int[] dp_left=new int[prices.length];   //dp_left[i]   i       
        int[] dp_right=new int[prices.length];  //dp_right[i]   i       
        //      
        dp_left[0]=0;
        int minbuy=prices[0];
        for(int i=1;i=0;i--){
            max=Math.max(prices[i],max);
            dp_right[i]=Math.max(dp_right[i+1],max-prices[i]);
        }
        int maxProfit=Integer.MIN_VALUE;
        for(int i=0;i