/**
 * @author xixing
 * @version 1.0
 * @date 2020/2/19 11:30
 */
public class N123 {
    public static int maxProfit(int[] prices) {

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

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


    }

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

    int dp[][][]=new int[prices.length][k+1][2];

    for(int i=0;i<prices.length;i++){
        for(int k1=k;k1>=1;k1--){
            if(i==0){
                dp[0][k1][0]=0;
                dp[0][k1][1] = -prices[i];
                continue;
            }
            dp[i][k1][0]=Math.max(dp[i-1][k1][0],dp[i-1][k1][1]+prices[i]);
            dp[i][k1][1]=Math.max(dp[i-1][k1][1],dp[i-1][k1-1][0]-prices[i]);
        }

    }

    return dp[prices.length-1][k][0];


}

public static int maxProfit(int k, int[] prices) {
    /**
     * java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
     *   at line 7, Solution.maxProfit
     *   at line 57, __DriverSolution__.__helper__
     *   at line 87, __Driver__.main
     */
    if(prices.length==0){
        return 0;
    }
    //当k>一半的时候，相当于可以每隔一天进行交易，直接调用122题的贪心算法即可

    if(k>prices.length/2){
        return maxProfit122(prices);
    }

    int dp[][][]=new int[prices.length][k+1][2];

    for(int i=0;i<prices.length;i++){
        for(int k1=k;k1>=1;k1--){
            if(i==0){
                dp[0][k1][0]=0;
                dp[0][k1][1] = -prices[i];
                continue;
            }
            dp[i][k1][0]=Math.max(dp[i-1][k1][0],dp[i-1][k1][1]+prices[i]);
            dp[i][k1][1]=Math.max(dp[i-1][k1][1],dp[i-1][k1-1][0]-prices[i]);
        }

    }

    return dp[prices.length-1][k][0];


}
public static int maxProfit122(int[] prices) {
    if (prices.length==0){
        return 0;
    }
    int temp=prices[0];
    int profile=0;
    for(int i=1;i<prices.length;i++){

        if(prices[i]>temp){
            profile=profile+prices[i]-temp;
            temp=prices[i];
        }else {
            temp=prices[i];
        }

    }
    return profile;
}

public class N220 {
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set=new TreeSet<Integer>();
        for(int i=0;i<nums.length;i++){
            //找出树里面比nums[i]大的最小数
            Integer s=set.ceiling(nums[i]);
            if(s!=null&&s-t<=nums[i]){
                //测试用例有nums[i]与Integer.MAX_VALUE相等的，如果不判断会溢出
                // s-nums[i]<=t会溢出所以我们改成s-t<=nums[i]
                return true;

            }
            //找出树里面比nums[i]小的最大数
            s=set.floor(nums[i]);
            if(s!=null&&nums[i]<=t+s){
                return true;


            }
            set.add(nums[i]);
            if(set.size()>k){
                set.remove(nums[i-k]);
            }

        }

        return false;

    }

    public static void main(String[] args) {
        int[] nums={-1,2147483647};

        System.out.println(containsNearbyAlmostDuplicate(nums,3,2147483647));
    }

}