3287. 求出数组中最大序列值

李恒道

凹了三四个小时才明白
我操
不愧是2500分题
https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/description/

function maxValue(nums, k) {
  const MX = 1 << 7;
  const n = nums.length;
  //原本是三层，index，当前index排第几个数字，xor的结果
  //因为从右到左计算，排列的时候如果不选当前数字，则之前的结果依然要继承
  //所以可以忽略index，使用两层来依次递推
  let xorArr = new Array(k + 1).fill(0).map((i) => new Array(MX).fill(false));
  xorArr[0][0] = true;
  let suf = new Array(n - k);

  for (let index = nums.length - 1; index >= 0; index--) {
    const num = nums[index];
    //根据index遍历到结尾有多少元素，即多少可能
    //例如当前元素排第四，后面有两个元素
    //则后面的元素只可能是第二个，第一个，第零个，所以边界是n - k - 1
    //而为了插入当前元素，最大只能为k-1个，所以边界是k - 1
    //之所以倒序是因为如果为true，则会设置当前个数+1的某个位置为true
    //如果正序会导致顺序错误
    for (let rank = Math.min(k - 1, n - k - 1); rank >= 0; rank--) {
      for (let xorNum = 0; xorNum < MX; xorNum++) {
        if (xorArr[rank][xorNum]) {
          xorArr[rank + 1][xorNum | num] = true;
        }
      }
    }
    //比如k有2个，一共六个元素，这时一定只有0到4的下坐标符合要求
    //所以要判断n-k
    if (index <= n - k) {
      //拷贝k个数字的数组
      suf[index] = [...xorArr[k]];
    }
  }
  //与上方同理，计算前缀
  xorArr = new Array(k + 1).fill(0).map((i) => new Array(MX).fill(false));
  xorArr[0][0] = true;
  let pre = new Array(n - k);
  for (let index = 0; index < n - k; index++) {
    const num = nums[index];
    for (let rank = Math.min(k - 1, index); rank >= 0; rank--) {
      for (let xorNum = 0; xorNum < MX; xorNum++) {
        if (xorArr[rank][xorNum]) {
          xorArr[rank + 1][xorNum | num] = true;
        }
      }
    }
    if (index >= k - 1) {
      pre[index] = [...xorArr[k]];
    }
  }
  //计算前缀和后缀的xor
  let ans = 0;
  for (let rank = k - 1; rank < n - k; rank++) {
    for (let xorNum = 0; xorNum < MX; xorNum++) {
      if (pre[rank][xorNum]) {
        //取该位置之后的后缀
        for (let xorNumSuf = 0; xorNumSuf < MX; xorNumSuf++) {
          if (suf[rank + 1][xorNumSuf]) {
            //前缀和后缀都存在，取最大的ans
            ans = Math.max(ans, xorNum ^ xorNumSuf);
          }
        }
      }
    }
  }
  return ans;
}