1856.子数组最小乘积的最大值

链接：1856.子数组最小乘积的最大值
难度：Medium
标签：栈、数组、前缀和、单调栈
简介：给你一个正整数数组  nums ，请你返回  nums  任意   非空子数组   的最小乘积   的   最大值  。

题解 1 - typescript

• 编辑时间：2021-07-19
• 执行用时：352ms
• 内存消耗：67.2MB
• 编程语言：typescript
• 解法介绍：单调栈，获取两边的最大值，由于 js 最多表示 53 位，需要用 bigint。

function maxSumMinProduct(nums: number[]): number {
  const n = nums.length;
  const l = new Array(n).fill(-1);
  const r = new Array(n).fill(n);
  const stack: number[] = [];
  const sums: number[] = [0];
  let sum = 0;
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    sums.push((sum += num));
    while (stack.length && nums[stack[stack.length - 1]] >= num) r[stack.pop()!] = i;
    if (stack.length) l[i] = stack[stack.length - 1];
    stack.push(i);
  }
  let ans = 0n;
  for (let i = 0; i < n; i++) {
    const num = (BigInt(sums[r[i]]) - BigInt(sums[l[i] + 1])) * BigInt(nums[i]);
    ans = ans > num ? ans : num;
  }
  ans %= BigInt(10 ** 9 + 7);
  return Number(ans);
}