求数组中区间中最小数*区间所有数和的最大值
程序员文章站
2022-05-12 10:34:02
...
给定一个数组序列,使得区间经过如下计算的值是所有区间中最大的:区间中的最小数*区间所有数的和
如[6,2,1],则求出区间为[6]
输入:
3
6 2 1
输出:
36
大体思路:
给定一个数组序列,
使得区间经过如下计算的值是所有区间中最大的:
区间中的最小数*区间所有数的和
如[6,2,1],则求出区间为[6]
输入:
3
6 2 1
输出:
36
大体思路: 把每个数字看成最小值,
因为所有数大于0,符合条件的区间越大值越高
扫左扫右,得到边界(第一个小于arr[i]的)
最后依次判断得到答案
public class test {
public static int function(int[] arr) {
int len = arr.length;
int[] sum = new int[len];
int ans = 0;
for (int i = 0; i < len; i++) {
//右边界
sum[i] = arr[i];
for (int j = i+1; j < len; j++) {
if (arr[j] >= arr[i]) {
sum[i] += arr[j];
} else {
break;
}
}
//左边界
for (int 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;
}
}
上一篇: 3个整数中最大的数和最小的数
下一篇: python中logging的使用