求区间最小数乘区间和的最大值

发表于 | 分类于 |
字数统计: 309 字 | 阅读时长 ≈ 1 分钟

题目描述：给定一个数组，要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和。数组中的元素都是非负数。

输入两行，第一行n表示数组长度，第二行为数组序列。输出最大值。

1
2
3
4
5
6
输入
3
6 2 1
输出
36
解释：满足条件区间是[6] = 6 * 6 = 36;

暴力

把每个数字看成最小值，因为所有数大于0，符合条件的区间越大值越高，扫左扫右，得到边界（第一个小于arr[i]的），最后依次判断得到答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function enum_method(arr) {
  let len = arr.length;
  let sum = []; // 求和
  let ans = 0;
  for (let i = 0; i < len; i++) {
    //右边界
    sum[i] = arr[i];
    for (let j = i + 1; j < len; j++) {
      if (arr[j] >= arr[i]) {
        sum[i] += arr[j];
      } else {
        break;
      }
    }
    //左边界
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] >= arr[i]) {
        sum[i] += arr[j];
      } else {
        break;
      }
    }
    ans = Math.max(ans, sum[i] * arr[i]);
  }
  return ans;
}

console.log(enum_method([6, 2, 1]))

复杂度分析

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)。使用sum这个数组暂存数据