给定一个数组和一个正整数N，求一个和小于N的最长连续子数组

Question

给定一个数组和一个正整数N，求一个和小于N的最长连续子数组

头条算法题

相关代码

// 请把代码文本粘贴到下方（请勿用图片代替代码）

大神!!! 思路，代码，注释

Answer 1

function lsa_n(arr, n) {
    if (arr.length <= 0) { return [] }

    let sum = [0];
    // 前 i 项和；
    // sum[i] = arr[0] + arr[1] + ... + arr[i-1]
    // 因此，arr [i, j) 之间的子数组和为 sum[j] - sum[i]

    // stk ，见下。
    let stk = [0];
    let s = 0;
    for (let i = 0; i < arr.length; i++) {
        // 生成 sum
        s += arr[i];
        sum[i + 1] = s;

        // 维护 stk ：
        // 在将 i+1 加入 stk 前，移除 stk 中所有 sum[stk[.]] <= stum[stk[i+1]] 的元素
        let top = stk[stk.length - 1];
        while (stk.length > 0 && s <= sum[top]) {
            top = stk.pop();
        }
        stk.push(i + 1);
    }
    // 经过以上处理：
    // 1. sum[stk[i]] 严格单调增加
    //    对任何 i < j , sum[stk[i]] < sum[stk[j]]
    // 2. arr.length 在 stk 数组中
    // 3. 对任何 stk[i] < k < stk[i+1] ，sum[stk[i+1]] <= sum[k]
    //    证： （反证）
    //         若存在 stk[i] < k < stk[i+1], sum[stk[i+1]] > sum[k], 
    //         另其中使sum[k]最小的一个 k 中，最后一个为 k0 。
    //         于是，处理 k0 时，k0 被加入 stk （每一个都会先被被加入,stk.push 是无条件的）
    //         在处理任何 k0 < l <= stk[i+1] 时，由于 sum[l] > sum[k0] （假设条件），k0 不会被从 stk 中弹出，即 k0 最终将在 stk 中。
    //         这与 stk[i] < k0 < stk[i+1] 矛盾（k0 不在 stk 中）
    //         所以原假设不成立
    // 4. 若和最长的子数组为 [i, j) ，则 j 在 stk 中。
    //    证： （反证）
    //         如果 j 不在 stk 中，则存在 l ,使得 stk[l] > j （arr.length 在 stk 中）
    //         设最小的一个 l 为 l0 。
    //         如 l0 == 0 ，易知 sum[stk[l0]] = sum[stk[0]] <= sum[j] 。（证明与 3 类似）
    //         如果 l0 > 0 ，则 stk[l0-1] < j < stk[l0] ，依然有 sum[stk[l0]] <= sum[j]。
    //         于是 ,sum[stk[l0]] - sum[i] <= sum[j] - sum[i] < n，
    //         即 [i, stk[l0]) 也是一个符合条件的子数组。
    //         但该子数组比 [i, j) 要长，矛盾。
    //         所以原假设不成立。

    let start = 0;
    let end = 0;
    let max_len = 0;
    let max_s = 0;
    let max_e = 0;
    while (true) {
        // 求以 start 开始的最长连续子数组
        //    终点一定在 stk[] 中
        //    由于 sum[stk[]] 严格单调增加
        //    循环在 sum[stk[end]] - sum[start] >=n 后可终止
        // 注意 end 不是 arr 的下标，而是 stk 的下标
        while (end < stk.length && sum[stk[end]] - sum[start] < n) {
            if (stk[end] - start > max_len) {
                max_len = stk[end] - start;
                max_s = start;
                max_e = stk[end];
            }
            end++;
        }

        if (end === stk.length) {
            break;
        }

        // 如果以 start 开始的和小于 n 的最长连续子数组 为 [start, e = start + len)
        // 则对任何 s_new > start, 如果 sum[s_new] <= sum[start] ，
        // 其 和小于 n 的最长连续子数组长处不会超过 len 。
        // 证 : 否则，若 [s_new, e_new = s_new + len_new) 和小于 n ，且 len_new > len ，
        //     则， sum[e_new] - sum[s_new] < n
        //          sum[e_new] - sum[start] <= sum[e_new] - sum[s_new] < n
        //      而 e_new - start = s_new + len_new - start > len_new >= len 
        //      即 [start, e_new) 将是一个符合条件的数组且更长，
        //      与 [start, e) 是已 start 开始的符合条件的最长子数组矛盾
        // 所以，此处可以前移 start 至 sum[s_new] > sum[start]
        let s_new = start + 1;
        while (s_new < arr.length && sum[s_new] <= sum[start]) {
            s_new++;
        }
        start = s_new;
    }
    return arr.slice(max_s, max_e);
}

Answer 2

可以用动态规划的思想去看，

设 S(i) 为以第 i 个元素结尾的和小于 N 的最长连续数组
设 len(i) 为 S(i) 的长度
设 sum(i) 为 S(i) 的和

1. 边界：

   • len(0) = arr[0] < N ? 1 : 0
   • sum(0) = arr[0] （对于不可取的数（比 N 大）我们也把和记上）
2. 当计算 S(i) 时，如果 arr[i] >= N，那么舍弃

3. 否则

   1. 将 arr[i] 加入 S(i) 中（目前 len(i) 为 1, sum(i) 为 arr[i]）

   2. 不停归并 S(i) 左边相邻的 S(i-len(i)) ，直到 sum(i) 不再小于 N

      1. 这里需要注意对于一些比 N 大的项原来不可取，现在也有可能取到
   3. 最后从 S(i) 最左的元素往右筛除，缩小数组直到总和小于 N

最后根据最长的 len 返回数组即可

function lsa (arr, n) {
  if (arr.length <= 0) { return [] }

  // 1
  const len = [arr[0] < n ? 1 : 0]
  const sum = [arr[0]]

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] >= n) { // 2
      len[i] = 0
      sum[i] = arr[i]
    } else { // 3
      // 3.1
      len[i] = 1
      sum[i] = arr[i]
      // 3.2
      for (let j = i - len[i]; j  >= 0 && sum[i] < n; j = i - len[i]) {
        sum[i] += sum[j]
        len[i] += len[j] || 1 // 3.2.1
      }
      // 3.3
      for (let j = i + 1 - len[i]; j < i && sum[i] >= n; j++) {
        len[i] -= 1
        sum[i] -= arr[j]
      }
    }
  }

  const max = len.reduce((max, l, i) => l > len[max] ? i : max, 0)

  return arr.slice(max + 1 - len[max], max + 1)
}

Answer 3

function getMaxSubArr(arr, target) {
  if (arr.length === 1) {
    return arr[0] < target ? arr : [];
  }
  const dp = [[arr[0]]];
  for (let i = 1; i < arr.length; i++) {
    const c = arr[i];
    const lastDp = dp[i - 1];
    const sum = lastDp.reduce((acc, cur) => acc + cur, 0);
    // 理想情况，直接追加
    if (c + sum < target && lastDp[lastDp.length - 1] === arr[i - 1]) {
      dp[i] = [...dp[i - 1], c];
    } else {
    // 尝试往回找个更好的
      if (c < target) {
        const newArr = [];
        let sumDiff = target;
        let j = i;
        let newItem = arr[j];
        while (j >= 0 && sumDiff >= newItem) {
          sumDiff -= newItem;
          newArr.unshift(newItem);
          j--;
          newItem = arr[j];
        }
        dp[i] = dp[i - 1].length > newArr.length ? dp[i - 1] : newArr;
      } else {
      // 都比target大了，无话可说
        dp[i] = dp[i - 1];
      }
    }
  }
  return dp[arr.length - 1];
}