数组划分前缀和滑动窗口子数组、序列问题

689!!!高频题找到三个长度为k互不重叠的子数组的最大和

Input: [1,2,1,2,6,7,5,1], 2
不重叠窗口为2的数组的和 [1, 2], [2, 6], [7, 5]
返回起始索引为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

https://leetcode.com/articles/maximum-sum-of-3-non-overlapping-intervals/
https://www.jiuzhang.com/solution/maximum-sum-of-3-non-overlapping-subarrays/

53!!!最大subarray sum

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Kadane 14ms 19%

public int maxSubArray(int[] nums){
    int sum = nums[0],rst = nums[0];
    for(int i=1;i<nums.length;i++){
        sum = Math.max(nums[i],sum+nums[i]);
        rst = Math.max(rst,sum);
    }
    return rst;
}

greedy:

!!337 不可以抢父节点抢过的房子

不可以抢父节点抢过的房子，注意不是层

输入: [2,1,3,null,4]

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 4 = 7.

思路：每个node保存偷/不偷的最大值。如果这个点不偷，最大值是左偷/不偷最大值+右偷/不偷最大值。如果这个点偷，是这个点+左右不偷的最大值。

1ms 99%

public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}
private int[] robSub(TreeNode root) {
    if (root == null) return new int[2];
    
    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    int[] res = new int[2];

    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    
    return res;
}

加上Map<TreeNode,Integer> 12ms 36%

public int rob(TreeNode root) {
    if(root == null )return 0;
    int sum = root.val;

    if(root.left!= null)
        sum += rob(root.left.left) + rob(root.left.right);

    if(root.right!= null)
        sum += rob(root.right.left) + rob(root.right.right);

    return Math.max(sum, rob(root.left) + rob(root.right));
}

！309 只能卖掉再买，卖掉股票之后的一天不能买

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) 意思是可以不买不卖。
思路：一共有3买，卖，不动种操作，记录每天以这三个状态结尾的最大值。

public int maxProfit(int[] prices) {
    if(prices == null ||prices.length <1)return 0;
   int n = prices.length;
    int[] buy = new int[n];
    int[] rest = new int[n];
    int[] sell = new int[n];
    buy[0] = - prices[0];
    rest[0] = 0;
    sell[0] = 0;
    for(int i =1;i<n;i++){
        // 不操作 或者 已经休息了1次了再买
        buy[i] = Math.max(buy[i-1],rest[i-1] - prices[i]);
        // 只能前一次是卖
        rest[i] = sell[i-1];
        // 前一次是买 或者不操作
        sell[i] = Math.max(sell[i-1],buy[i-1] + prices[i]);
    }
    return sell[n-1];
}

lt 45 最大子数组差

给出数组[1, 2, -3, 1]，返回 6
找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大

724 最小划分数字分成2组和的差最小

给出nums = [1, 6, 11, 5]，返回1
// Subset1 = [1, 5, 6]，和是12
// Subset2 = [11]，和是11
// abs(11 - 12) = 1

dp：dp[n+1][sum+1] 用1~n前n个数字能得到sum

递归思路：
两种情况用这个数字和不用，终止条件:所有数字都选择过了。
超时

Map<String,Integer> difmemo;
public int findMindfs(int[] arr){
    int sum = 0;
    for (int i = 0; i < arr.length ; i++) {
        sum += arr[i];
    }
    difmemo = new HashMap<>();
    return dfs(arr, 0, 0, sum);
}
private int dfs(int[] arr,int idx,int sum,int target){
    if(idx == arr.length)
        return Math.abs(target  -  2* sum);
    if(difmemo.containsKey(idx+" "+sum))return difmemo.get(idx+" "+sum);
    difmemo.put(idx+" "+sum, Math.min(dfs(arr, idx+1, sum+arr[idx],  target),
            dfs(arr, idx+1, sum,  target))) ;
    return difmemo.get(idx+" "+sum);
}

813 数组A分成K个相邻的非空子数组，子数组平均和和最大多少

输入:
A = [9,1,2,3,9]
K = 3
输出: 20
解释:
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.

805 数组分成2个平均值相等的部分

最大值为k的不重叠子数组的长度和？??

https://www.geeksforgeeks.org/maximum-sum-lengths-non-overlapping-subarrays-k-max-element/

Input : arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4} k = 4
Output : 5
{2, 1, 4} => Length = 3
{3, 4} => Length = 2
So, 3 + 2 = 5 is the answer

public int lensum(int[] arr,int k){
    int n = arr.length;
    int ans = 0;

    for (int i = 0; i < n ; i++) {
        int cnt=0;
        int flag = 0;
        while (i<n&&arr[i]<=k){
            cnt++;
            if(arr[i] == k)flag = 1;
            i++;
        }
        //？？？
        if(flag == 1) ans+=cnt;
        while (i<n&&arr[i]>k)i++;
    }
    return ans;
}

198 不能偷相邻房屋最大利润

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4

122 可以买卖多次买股票的利润

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

123 最多买卖2次的买股票利润考到

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

188 最多k次买卖的买卖股票利润

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

重复元素很多的数组排序

https://www.geeksforgeeks.org/how-to-sort-a-big-array-with-many-repetitions/

AVL or Red-Black to sort in O(n Log m) time where m is number of distinct elements.
//todo

77combinations C(n,k)=C(n-1,k-1)+C(n-1,k)

C(n-1,k-1)表示选这个数，C(n-1,k)表示不选这个数
88%的写法：

public List<List<Integer>> combineFast(int n,int k) {
    List<List<Integer>> result = new ArrayList<>();
    if(k>n||k<0)return result;
    if(k==0){
        result.add(new ArrayList<>());
        return result;
    }
    result = combine(n-1,k-1 );
    for(List<Integer> list:result){
        list.add(n);
    }
    result.addAll(combine(n-1,k ));
    return result;
}

//    math 8% C(n,k)=C(n-1,k-1)+C(n-1,k)
public List<List<Integer>> combineMath(int n,int k){
    if(k==n||k==0){
        List<Integer> row = new ArrayList<>();
        for (int i = 1; i <=k ; i++) {
            row.add(i);
        }
        return new ArrayList<>(Arrays.asList(row));
    }
    List<List<Integer>> result = this.combineMath(n-1,k-1 );
    result.forEach(e->e.add(n));
    result.addAll(this.combineMath(n-1,k ));
    return result;
}

896有正负的数列判断单调

用首尾判断up/down，中间相邻遍历判断up/down和之前不符return false
20ms

public boolean isMonotonic(int[] A) {
    if (A.length==1) return true;
    int n=A.length;
    //关键
    boolean up= (A[n-1]-A[0])>0;
    for (int i=0; i<n-1; i++)
        if (A[i+1]!=A[i] && (A[i+1]-A[i]>0)!=up) 
            return false;
    return true;
}

753 输出能包含所有密码可能性的最短串

Input: n = 2, k = 2
Output: “00110” 包含了00,01,10,11

官方解
 de Bruijn Card Trick

方法1

每个点1次
写出n个数的组合(11,12,22,21) 并找出哈密尔顿路径
方法2

每条边1次
写出(n-1)个数的组合(1,2) 的完全图，找出欧拉环路(circuit)。de Bruijn 序列的数量为欧拉环的数量。
用k个数字，长度有n的组合有$k^n$种，但是因为可以首尾相连，总共de Bruijn的数量是
$\frac{k! k^{n-1}}{k^n}$
方法3 用不重复的最小字典序Lyndon Word
例子：
1.列出所有长度为4的组合1111,1112…以及能被4整除的长度(1,2)的组合1,2,11,22.
2.所有按字典序排序
3.去除所有旋转之后相同的组合，只保留字典序最小的：01和10只保留01

n = 6, k = 2
0 000001 000011 000101 000111 001 001011 001101 001111 01 010111 011 011111 1
连起来就是最小的de Bruijin sequence

!!!152 最大子数组乘积保留当前值之前的最大积和最小积

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

维护前缀乘积的min/max，每次当前数组元素必须参与运算。
注意：更新min/max的时候考虑放弃前缀，只考虑本身，所以变成子数组。
注意：子数组所以min/max是前一个index的结果

负数的最小积有潜力变成最大积
当前max是 nums[i]*max,nums[i]*min,nums[i] 三者的最大者
当前min是 nums[i]*max,nums[i]*min,nums[i] 三者最小值
更新全局max
4ms 11.99%

public int maxProduct(int[] nums) {
    int sum = nums[0],min = nums[0],max = nums[0];
    for(int i=1;i<nums.length;i++){
        int nextmax = nums[i]*max;
        int nextmin = nums[i]*min;
        max = Math.max(Math.max(nextmax,nextmin),nums[i]);
        min = Math.min(Math.min(nextmax,nextmin),nums[i]);
        sum = Math.max(max,sum);
    }
    return sum;
}

合唱团背包(只能向前找k个物品)+数组最大子数组(差d的子数组)???乘积

从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大
输入3
7 4 7
2 50
输出49

更新当前结尾最大子数组和需要试min/max取前d个数之内(可以跳过前d-1个)的全部结果

public static long maxability(int n,long[]arr,int k,int d){
    long[][] fmax = new long[k+1][n];
    long[][] fmin = new long[k+1][n];
    long res = Integer.MIN_VALUE;
    fmax[1] = arr.clone();
    fmin[1] = arr.clone();
      //选2-k个人
        for (int j = 2; j <=k ; j++) {
            for (int i = 0; i <n ; i++) {
            // 遍历上次层结果的[i-d,i)
            for (int l = i-1; l>=0&&l>=i-d ; l--) {
                // 前面以l结尾的最大和最小
                fmax[j][i] = Math.max(fmax[j][i],Math.max(fmax[j-1][l]*arr[i],fmin[j-1][l]*arr[i]) );
                fmin[j][i] = Math.min(fmin[j][i],Math.min(fmax[j-1][l]*arr[i],fmin[j-1][l]*arr[i]) );
            }
        }
    }
    for (int i = 0; i <n ; i++) {
        res = Math.max(res, fmax[k][i]);
    }
    return res;
    }

769 !!!!!最多能排序的块 0-n的排列切割，块排序后连接是排序的原数组

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

注意条件：arr that is a permutation of [0, 1, ..., arr.length - 1]
思路1:当前的index==当前的最大值，左边一共有index-1个数字，比index小的都在左边了，可以切分。

idx:0 1 2 3 4
arr:1 0 2 3 4
max:0 1 2 3 4
当前index<当前max 表示可以划分成一组，==max表示要换下一组

public int maxChunksToSorted(int[] arr) {
    int res = 0;
    for(int i =0,max = 0;i<arr.length;i++){
        if(i==(max=Math.max(max,arr[i])))
            res++;
    }
    return res;
}

思路2：维护一个leftmax和minright数组，当leftmax<=rightmin则可以划分

915 Max(left)<=Min(right)

画折线图，当前A[i]<left 则把切分线抬到globalMax

7ms 60%

public int partitionDisjoint(int[] A) {
    int n = A.length;
    int leftMax = A[0];
    int global = leftMax;
    int parti = 0;
    for(int i = 1;i<n;i++){
        if(leftMax>A[i]){
            leftMax = global;
            parti = i;
        }else global = Math.max(global,A[i]);
    }
    return parti+1;
}

768 最多能排序的块重复元素

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。

最快的100%：只构造后缀min数组,线性扫描更新max,保证leftMax<Rmin的划分

public int maxChunksToSorted100(int[] arr) {
    int n = arr.length;
    int[] minOfRight = new int[n];
    minOfRight[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        minOfRight[i] = Math.min(minOfRight[i + 1], arr[i]);
    }
    int res = 0;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n - 1; i++) {
        max = Math.max(max,arr[i]);
        // 等于 重复元素 去掉=就是第一题 68%
        if (max <= minOfRight[i + 1]) res++;
    }
    return res + 1;
}

56%：前缀max数组后缀min数组
left[2,1] right[3,4,4]
leftMax<rightMin的时候

arr     [2, 1, 3, 4, 4]

比较切分位置0~n-1：[0:i][i+1:n-1]
leftMax    [2, !2, !3, !4, 4] 
rightMin[1, 1, !3, !4, !4]

public int maxChunksToSorted(int[] arr) {
    int n = arr.length;
    int[] maxLeft = new int[n];
    int[] minRight = new int[n];
    maxLeft[0] = arr[0];
    for (int i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1],arr[i]);
    }
    minRight[n-1] = arr[n-1];
    for (int i = n-2; i >= 0 ; i--) {
        minRight[i] = Math.min(minRight[i+1],arr[i]);
    }

    int res = 0;
    for (int i = 0; i < n-1; i++) {
        if(maxLeft[i] <= minRight[i+1]){
            res++;
        }
    }
    return res+1;
}

44%拷贝一个数组排序，做累加,相等则可以划分
[2,1 |,3 |,4 |,4]
[1,2 |,3 |,4 |,4]

public int maxChunksToSorted(int[] arr) {
    int sum1 =0,sum2 =0,res = 0;
    int[] copy = arr.clone();
    for(int i =0;i<arr.length;i++){
        sum1 += copy[i];
        sum2 += arr[i];
        if(sum1 == sum2)ans++;
    }
    return ans;
}

581 需要排序的最小子串，整个串都被排序了递增

40大于35，只排序到右边遍历过来第一个n<n-1是不够的
要找到[30~31]中的min和max

public static int fid(int[]A){
    //1,3,2,2,2
    int n = A.length, beg = -1, end = -2, min = A[n-1], max = A[0];
    for (int i=1;i<n;i++) {
        max = Math.max(max, A[i]);//从前往后，找到最大值max=3
        min = Math.min(min, A[n-1-i]);//从后往前找到最小值min=2
        if (A[i] < max) end = i; //a=2<3 end = 2->3->4 直到找到a[i]>max
        if (A[n-1-i] > min) beg = n-1-i;//begin =1 直到找到a[i]<min
    }
    return end - beg + 1;
    }

697 ？？保留数组中最高频出现数字频数的最短数组长度

Input: [1,2,2,3,1,4,2]
最小连续子数组，使得子数组的度与原数组的度相同。返回子数组的长度
Output: 6 最高频是2->【2,2,3,1,4,2】

用3个hashmap扫一遍记录每个数字出现的cnt,left,right
最后cnt最大的right-left+1
合并成一个hashmap<Integer,int[3]>

！！416 数组分成两部分（不连续) sum相等。list的总sum为奇数则不可能。

public boolean canPartition(int[] nums){
    int sum = 0;
    for(int n : nums){
        sum+=n;
    }
    if(sum%2!=0)return false;
    int[] dp = new int[sum+1];
    dp[0] = 1;
    for(int n : nums){
        for(int v = sum;v>=0;v--){
            if(dp[v]==1)dp[v+n]=1;
        }
        if(dp[sum/2]==1)return true;
    }
    return false;
}

!594 最长max min相差1的子序列(不是连续的数组)

数组 hashmap 计数模板

689!!!高频题 找到三个长度为k互不重叠的子数组的最大和