package com.lxf.test;

import java.util.*;

public class MaxProfitK {
    public static void main(String[] args) {
        //2
        //1,2,4,2,5,7,2,4,9,0
		System.out.println(maxProfit(2,new int[]{1,2,4,2,5,7,2,4,9,0}));
    }

    public static int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        //treemap只能排序value,和我的需求不一致
        //存储prices的所有低进高出的卖出收益,key：低进的下标,value:高出的时候卖出的价格
//    	TreeMap<Integer, Integer> map=new TreeMap<Integer, Integer>(new Comparator<Integer>() {
//    		public int compare(Integer a, Integer b) {
//    			return Integer.compare(a, b);
//    		};
//		});
		//存储股票卖出时的下标对应每一个连续上升的收益
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int pre = -2;
        for (int i = 0; i < prices.length - 1; i++) {
        	//当前连续上升的收益
            int m = 0;
            //连续比较，获取差值
            while (i < prices.length - 1 && prices[i] < prices[i + 1]) {
                m += prices[i + 1] - prices[i];
                i++;
            }
            if (m > 0) {
            	//判断是否需要合并前一个收益(k<map.size())
                if (pre > 0 && prices[pre] < prices[i]) {
                    map.put(i, m + map.get(pre));
                    map.put(pre, 0);
                } else {
					map.put(i, m);
                }
                pre = i;
            }
        }
        //存储每一个连续上升的收益并排序
        LinkedList<Integer> linkedLists = new LinkedList<Integer>(map.values());
        Collections.sort(linkedLists, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o2, o1);
            }
        });
		//将链表中较小移除(如果k<map.size()，移除map.size()-k个)
        if (k < linkedLists.size()) {
            for (int i = linkedLists.size() - 1; i > k - 1; i--) {
                linkedLists.pollLast();
            }
        }
		//获取k个收益的对应的下标(卖出时)
		List<Integer> indexs=new ArrayList<Integer>();
        for (Integer key : map.keySet()) {
            if (linkedLists.contains(map.get(key))) {
                indexs.add(key);
            }
        }

        int pY = -prices[0];
        int pN = 0;
        for (int i = 1; i < prices.length; i++) {
        	//只有在indexs集合中的下标才卖出股票
            if (indexs.contains(i)) {
                pN = Math.max(pN, pY + prices[i]);
            }
            pY = Math.max(pY, pN - prices[i]);
        }
        return pN;
    }

}

2. 动态规划(官方题解)

class Solution {
    public int maxProfit(int k, int[] prices) {
    	int n = prices.length;
        if (n == 0) {
            return 0;
        }
        //n天，最多只能进行n/2笔交易
        //取k和n/2的最小值
        k = Math.min(k, n / 2);
        //buy:买进股票时的收益
        //sell:卖出股票时的收益
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];
		//赋值初始值
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }
		//dp过程
        for (int i = 1; i < n; ++i) {
        	//第i轮第一笔交易(买进或者不卖出)
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            //进行第i轮k-1次交易
            for (int j = 1; j <= k; ++j) {
            	//买进
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);		//卖进
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }

        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        if