给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
[6] = 6 * 6 = 36;
[2] = 2 * 2 = 4;
[1] = 1 * 1 = 1;
[6,2] = 2 * 8 = 16;
[2,1] = 1 * 3 = 3;
[6, 2, 1] = 1 * 9 = 9;
从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。
区间内的所有数字都在[0, 100]的范围内;
第一行输入数组序列长度n，第二行输入数组序列。 对于 50%的数据, 1 <= n <= 10000; 对于 100%的数据, 1 <= n <= 500000;
输出数组经过计算后的最大值。
3 6 2 1
36
#include<iostream>
#include<vector>
using namespace std;
int main() {
int eNum = 0;
scanf("%d", &eNum);
int* list = new int[eNum];
int count[101] = { 0 };
for (int i = 0; i < eNum; i++) {
scanf("%d", &list[i]);
count[list[i]]++;
}
vector<int> num;
for (int i = 0; i < 101; i++) {
if (count[i] != 0)
num.push_back(i);
}
int max = 0;
for (int i = 0; i < num.size(); i++) {
int min = 100;
int sum = 0;
for (int j = 0; j <= eNum; j++) {
if (list[j] < num[i] || j == eNum) {
max = min * sum > max ? min*sum : max;
sum = 0; min = 100;
}
else {
min = min < list[j] ? min : list[j];
sum += list[j];
}
}
}
printf("%d", max);
return 0;
} 首先对数据进行桶排序，然后根据桶里的元素对数组进行遍历，当当前遍历的数组元素大于当前桶的值时，对区间进行计算。桶排可以过滤掉定义域内数组中没有出现的元素，不过由于样本数量比较大，基本上每个数据都会出现一次故其实这一步可以省略。
if __name__ == '__main__':
n=int(input())
array=list(map(int,input().split(" ")))
result=0
for i in range(n):
sum=array[i]
j=i-1
k=i+1
while(j>=0):
if array[j]>=array[i]:
sum+=array[j]
j=j-1
else:
break
while(k<n):
if array[k]>=array[i]:
sum+=array[k]
k=k+1
else:
break
result=max(result,sum*array[i])
print(result) 单调队列，两边延展。
#include <bits/stdc++.h>
using namespace std;
int num[500000];
int sum[500000];
int lt[500000];
int rt[500000];
stack<pair<int,int>> S;
stack<pair<int,int>> SR;
int sum_of(int l, int r){
if (l == 0)return sum[r];
else return sum[r] - sum[l - 1];
}
int main(){
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++){
scanf("%d", &num[i]);
if(i == 0){
sum[i] = num[i];
} else {
sum[i] = sum[i - 1] + num[i];
}
}
for (int i = 0; i < N; i++){
while(!S.empty() && S.top().second >= num[i]){
S.pop();
}
if(!S.empty()){
lt[i] = S.top().first + 1;
}else{
lt[i] = 0;
}
S.push(make_pair(i,num[i]));
}
for (int i = N - 1; i >= 0; i--){
while(!SR.empty() && SR.top().second >= num[i]){
SR.pop();
}
if(!SR.empty()){
rt[i] = SR.top().first - 1;
} else{
rt[i] = N - 1;
}
SR.push(make_pair(i,num[i]));
}
long long ans = 0;
for (int i = 0; i < N; i++){
ans = max(ans, (long long)sum_of(lt[i],rt[i]) * (long long)num[i]);
}
cout<<ans<<endl;
return 0;
}
考虑到每一个答案都是由一个区间的最小值×区间和得出
那么在一个给定的区间最小值情况下，最优情况一定是这个区间尽可能的延伸，直至区间最小值不满足给定值。
题目中数组里的数范围是[0, 100]。所以我们对每一个可能的区间最小值扫描一遍数组，每找到一个符合条件的区间就更新答案。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;
int a[MAX_N];
int main() {
long long ans, sum;
int n, minnum;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
a[n] = 0;
ans = 0;
for (int j = 100; j >= 1; j--) {
sum = 0, minnum = 101;
for (int i = 0; i <= n; i++) {
if (a[i] < j) {
ans = max(ans, sum * minnum);
minnum = 101, sum = 0;
}
else {
sum += a[i];
minnum = min(minnum, a[i]);
}
//printf("i = %d, j = %d, ans = %lld\n", i, j, ans);
}
}
printf("%lld\n", ans);
return 0;
} #如果当前数小于栈顶元素，或者遍历结束但栈不为空，栈顶元素出栈，作为区间最小值，同时它也是区间的右边界，区间的左边界为出栈后栈顶下标-1。 #如果栈为空或者当前数大于等于栈顶元素，下标入栈 n = int(input()) value = list(map(int,input().split())) p = [value[0]] for i in range(1,n): #预处理累计求和 p.append(p[i-1] + value[i]) ans = 0 stack = [0] for i in range(1,n): while stack and value[stack[-1]]>=value[i]: # 栈非空且栈顶元素大于当前元素，为了维持单调递增栈，弹出栈顶元素 min_num = value[stack.pop()]# 栈顶元素为区间最小值，出栈。左边界为栈顶或者空 ans = max(ans,(p[i-1]-(p[stack[-1]] if len(stack)>0 else 0))*min_num) stack.append(i) print(ans)
import java.util.Scanner;
import java.util.Stack;
public class Main {
/*区间最小值与区间之和相乘的最大值*/
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
int n = scanner.nextInt ();
int[] arr = new int[n];
int[] sum = new int[n+1];//累加和
sum[0] = 0;
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt ();
sum[i+1] = arr[i]+sum[i];
}
int[][] help = new int[n][2];
Stack<Integer> s = new Stack<> ();
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
while (!s.isEmpty ()&&arr[i]<=arr[s.peek ()]){
int j = s.pop ();
help[j][0] = s.isEmpty ()?-1:s.peek ();
help[j][1] = i;
}
s.push (i);
}
while (!s.isEmpty ()){
int tmp =s.pop ();
help[tmp][0] = s.isEmpty ()?-1:s.peek ();
help[tmp][1] = n;
}
for (int i = 0; i < help.length; i++) {
int left = help[i][0];
int right = help[i][1];
max = Math.max (max,arr[i]*(sum[right]-sum[left+1]));
}
System.out.println (max);
}
}
//参考自程序员代码面试指南。单调栈结构+辅助数组存储累加和，时间复杂度n，每个数组元素只需要入栈出栈一次。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int mymax(vector& num, int left, int right)
{
if(left == right) return num[left]*num[left]; //若区间内仅有一个数，结束递归
bool flag = true;
for(int i=left;i<right;i++)
if(num[i] != num[i+1])
{
flag = false;
break;
}
if(flag) return num[left]*num[left]*(right-left+1); //若区间内的数全部相等，结束递归
int result = num[left];
int minval = num[left];
int pos = left;
for(int i = left+1;i<=right;i++) //搜索区间内的最小值
{
if(num[i]<minval)
{
minval = num[i];
pos = i;
}
result += num[i];
}
result = result * minval; //计算当前区间
if(pos != left) result = max(result, mymax(num, left, pos-1)); //计算最小值左边
if(pos != right) result = max(result, mymax(num, pos+1, right)); //计算最小值右边
return result;
}
int main()
{
int n;
cin >> n;
vector num(n, 0);
for(int i=0;i> num[i];
int left = 0;
int right = n - 1;
cout << mymax(num, left, right);
return 0;
}
欢迎大佬来改进！
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> arr(n,0);
for(int i=0;i<n;i++)
cin>>arr[i];
vector<int> sum(n+1,0); //前缀和，sum[i]表示arr[0]...arr[i-1]之和（不含arr[i]）
sum[0]=0;
for(int i=1;i<=n;i++) {
sum[i]+=sum[i-1]+arr[i-1];
}
vector<int> left(n,0); //left[i]：当以arr[i]为最小值时所能形成的区间的左边界
vector<int> right(n,0); //right[i]:当以arr[i]为最小值时所能形成的区间的右边界
//左右边界为闭区间（包含）
stack<int> s; //单调栈
for(int i=1;i<n;i++) {
while(!s.empty() && arr[s.top()]>arr[i]) {
int x=s.top(); s.pop();
//栈顶元素比当前值大，所以栈顶元素为min时的右边界必为i-1
right[x]=i-1;
}
if(!s.empty()) {
int x=s.top(); //此时栈顶arr[x]<=arr[i]，所以arr[i]的左边界为x+1（等号不用担心，重复的值必有一个会取到包含这些重复数的最大区间）
left[i]=x+1;
}else{//左边不存在其他值比当前值小，所以直接拉到0
left[i]=0;
}
s.push(i);
}
while(!s.empty()) {
int x=s.top(); s.pop();
right[x]=n-1;
}
int res=0;
for(int i=0;i<n;i++) {
res=max(res,arr[i]*(sum[right[i]+1]-sum[left[i]]));
}
cout<<res;
return 0;
} 思路
每个元素都可能是某个或多个区间的最小值，所以当最小值确定的时候，区间越大越好，可以固定每个最小值，然后找区间左边界和右边界。
#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
// 每次假设当前为最小
int cur_max = -1;
for(int i=0; i<n; i++){
// 假设nums[i]是某个区间的最小值，那么这个区间应该越大越好，所以可以来找区间的左边界和右边界
int l = i;
while(l>=0 && nums[l]>=nums[i]) l--;// 确定左边界
int r = i;
while(r<n && nums[r]>=nums[i]) r++;// 确定右边界
int sum = accumulate(nums.begin()+l+1, nums.begin()+r, 0);
cur_max = max(cur_max, sum*nums[i]);
}
cout<<cur_max<<endl;
return 0;
}
# 为了找到所有“最大的”点，可以遍历点集合 P，对于每个点 x，检查是否满足所有其他点都不在 x 的右上方区域内。 def find_max_points(points):
def is_max_point(p, others):
for other in others:
if other[0] > p[0] and other[1] > p[1]:
return False
return True
max_points = []
for i in range(len(points)):
if is_max_point(points[i], points[:i] + points[i+1:]):
max_points.append(points[i])
return max_points
points = [(1, 2), (2, 3), (3, 1), (4, 4), (5, 3)]
result = find_max_points(points)
print(result) 用了以下三种方法，通过率分别为20%， 50%， 60%，看来python还是太慢了。。。 n = int(input()) inp = list(map(int, input().split())) max_num = 0 ''' ## brute force method O(n^3) for i in range(1,n+1): for j in range(0,n-i+1): temp = min(inp[j:j+i]) * sum(inp[j:j+i]) if temp > max_num: max_num = temp ''' ''' ## O(n^2) for i in range(n): left_index = i right_index = i while left_index > 0: if inp[left_index -1] < inp[i]: break else : left_index -= 1 while right_index < n-1: if inp[right_index +1] < inp[i]: break else : right_index += 1 temp = min(inp[left_index:right_index+1]) * sum(inp[left_index:right_index+1]) if temp > max_num: max_num = temp ''' # O(n) for i in range(0,101): min_num = 101 sum1 = 0 for j in range(n): if inp[j] < i : max_num = max(max_num, sum1 * min_num) sum1 = 0 min_num = 101 else : sum1 += inp[j] min_num = min(min_num, inp[j]) print(max_num)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
String[] s = sc.nextLine().split(" ");
int[] arr = new int[n];
int[] preSum = new int[n + 1];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(s[i]);
preSum[i + 1] = preSum[i] + arr[i];
}
int ans = 0;
//[j + 1] - [i]
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
int minIndex = stack.pop();
int min = arr[minIndex];
int l = !stack.isEmpty() ? stack.peek() : -1;
l += 1;
int r = i - 1;
ans = Math.max(ans, (preSum[r + 1] - preSum[l]) * min);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int minIndex = stack.pop();
int min = arr[minIndex];
int l = !stack.isEmpty() ? stack.peek() : -1;
l += 1;
int r = n - 1;
ans = Math.max(ans, (preSum[r + 1] - preSum[l]) * min);
}
System.out.println(ans);
}
}单调栈取最小数
前缀和快速算Sum
def max_val(li):
if len(li) == 1:
return li[0]**2
m = min(li)
ind = li.index(m)
if ind == 0:
return max(sum(li)*m,max_val(li[1:]))
elif ind == len(li) - 1:
return max(sum(li)*m,max_val(li[:-1]))
else:
return max(sum(li)*m,max_val(li[:ind]),max_val(li[ind+1:]))
n = int(input())
nums = list(map(int,input().strip().split(' ')))
print(max_val(nums))
用递归做的，跑到第七组的时候内存超了。。。。 # 思路：遍历每一个元素，保证当前元素为最小值，然后向两边扩展 while True: try: length = int(input()) nums = list(map(int, input().split())) max_v = -1 pos = 0 while pos < length: left, right = pos - 1, pos + 1 count = nums[pos] if not count: # 关键的一步，必须有，否则超时 if count > max_v: max_v = count pos += 1 continue while left >= 0 and nums[left] >= nums[pos]: count += nums[left] left -= 1 while right < length and nums[right] >= nums[pos]: count += nums[right] right += 1 if count * nums[pos] > max_v: max_v = count * nums[pos] pos += 1 print(max_v) except Exception as e: break
#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N];
stack<int> cur,l; //cur是单调栈，l是和cur同步的栈，记录cur中元素的左边比它大的数的和
int tempSum=0;
int n;
int ans=0;
void POP()
{
int num=cur.top(); cur.pop();
int leftOfNum=l.top();l.pop();
int all=leftOfNum+num+tempSum; //左+中+右
ans=max(ans,num*all);
tempSum+=num+leftOfNum;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
a[n]=0;
//定义一个组的中心是组中最小的数，这样就可以用单调栈
tempSum=0;
for(int i=0;i<=n;i++)
{
//把当前数左边（比它大）部分的pop出去,并把左边的值存用来计算tempSum，pop完后会tempSum入l栈并归零
//右边的会比它先弹出去并计算出新的tempSum，等到它被pop需要计算和时tempSum就是右边的和了
int num=a[i];
while(!cur.empty()&&cur.top()>num)
POP();
cur.push(num);
l.push(tempSum);
tempSum=0;
}
cout<<ans;
}
/*
6
1 3 4 2 6 5
*/ 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
