7006. 销售利润最大化.txt

https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/description/

动态规划 

public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        offers.forEach(list -> {
            if (!map.containsKey(list.get(1))) {
                List ll = new ArrayList();
                ll.add(new int[]{list.get(0), list.get(2)});
                map.put(list.get(1), ll);
            } else {
                map.get(list.get(1)).add(new int[]{list.get(0), list.get(2)});
            }
        });
        // 数组moneyArr表示下标不超过i的房子能卖的最大金额
        int[] moneyArr = new int[n + 1];
        // 第i个房子不卖，f[i]=f[i-1]
        // 第i个房子要卖，f[i]=MAX(f[i(start)]+money)
        // 优化表述为f[i+1]=...
        moneyArr[0] = 0;//下标不超过0的房子最多卖多少钱
        for (int i = 1; i < moneyArr.length; i++) {
            moneyArr[i] = moneyArr[i - 1];//1 不卖，钱和i-1一样
            // 2 卖
            if (map.containsKey(i - 1)) {
                // 取所有end为i的买家
                for (int[] arr : map.get(i - 1)) {
                    // 遍历买家，考察每一次买的钱的最大值。既然要买，那么获取对应买家的start为end的最大值，加上本次的金额，最终取最大值
                    // moneyArr[arr[0]] 取本次买家的start，获得以moneyArr[start]的值，再加上本次能卖的钱
                    moneyArr[i] = Math.max(moneyArr[i], moneyArr[arr[0]] + arr[1]);
                }
            }
        }
        return moneyArr[n];
    }