import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class LongestIntergratedLength {
    public static int getLIL1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int len = 0;

        for (int start = 0; start < arr.length; start++) {
            for (int end = start; end < arr.length; end++) {

                if (isIntergrated(arr, start, end)) {
                    len = Math.max(len, end - start + 1);
                }
            }
        }
        return len;
    }

    public static boolean isIntergrated(int[] arr, int left, int right) {
        int[] newArr = Arrays.copyOfRange(arr, left, right + 1);
        Arrays.sort(newArr);
        for (int i = 1; i < newArr.length; i++) {
            if (newArr[i - 1] != newArr[i] - 1) {
                return false;
            }
        }
        return true;
    }

    public static int getLIL2(int[] arr, int left, int right) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = 0;
        int max = 0;
        int min = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int L = 0; L < arr.length;L++){
            set.clear();
            max = Integer.MIN_VALUE;
            min = Integer.MAX_VALUE;
            for(int R = L;R < arr.length;R++){
                //arr[L...R]出现重复值
                if(set.contains(arr[R])){
                    break;
                }
                //arr没有出现重复值
                set.add(arr[R]);
                max = Math.max(max,arr[R]);
                min = Math.min(min,arr[R]);
                if(max- min == R - L){//是可整合的
                    len = Math.max(len,R-L+1);
                }
            }
        }
        return len;
    }
}

public class BestTimetoBuyandSellStock {
    public int maxProfit(int[] prices){
        if(prices == null || prices.length == 0){
            return 0;
        }
        int min = prices[0];
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min,prices[i]);
            ans = Math.max(ans,prices[i]);
        }
        return ans;
    }
}

第i个位置比第i-1个位置大 就买，只要有钱就买 就是最大

dp[i][j]表示arr[0…i]交易次数小于等于j次的最大钱数
(1)i号不参与任何交易 。。。arr[0…i][j] = arr[0…i-1][j]
(2) i号参与交易 i号卖出去 arr[0…i][j] （贪心）
在（2）的情况下 (i)dp[i-1][j-1] +[i]-[i] 前i-1次 买了有卖了i股票
(ii)dp[i-1][j-1]+[i]-[i-1]
…
dp[k][j-1]+[i]-[k] 每一个k 。。每一个[k]都要加，可以提出来 最后处理

public class BestTimetoBuyandSellStockFollow {
    public static int dp(int K,int[] prices){
        if(prices == null || prices.length == 0){
            return 0;
        }
        int N = prices.length;
        if(K >= N/2){
            //上一题答案，我csdn这个页面上 上一个 能买就买就行了
            return allTrans(prices);
        }

        int ans = 0;
        int[][] dp = new int[N][K+1];
        for(int j = 1;j <= K;j++){
            int t = dp[0][j-1] - prices[0];
            for(int i = 1;i < N;i++){
                t= Math.max(t,dp[i][j-1] - prices[i]);
                dp[i][j] = Math.max(dp[i-1][j],t+prices[i]);
                ans = Math.max(ans,dp[i][j]);
            }
        }
        return ans;
    }
}