选区间

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * n的范围[1,500000]太大，直接dp会超时
 *
 * 因为区间计算值都是由 区间最小值*区间和 得到的，
 * 所以在给定区间最小值的情况下，最优的情况一定是这个区间尽可能的扩展，
 * 直至区间的最小值不满足给定的最小值。
 * (扩展的过程因为满足 区间最小值 >= 给定区间最小值 的情况下，
 *      区间和一直增大，所以最终结果也增大)
 *
 * 又因为所有的数字都在[0, 100]的范围内，
 * 所以只需要遍历每一个数字为区间最小值的情况即可。
 *
 * 例如有序列[11, 12, 13, 1, 20, 21, 2, 30]，设i表示给定的区间最小值
 * 当i=10时，即规定 区间最小值 >= 10，
 *     满足区间的条件有[11, 12, 13], [20, 21], [30]
 *     对应的计算值为 11*(11+12+13), 20*(20+21), 30*30
 *     在给定i=10的情况下，最优值为max(11*(11+12+13), 20*(20+21), 30*30)
 * 所以对i所有可能的情况都遍历一遍就能确定最终的最优值，i属于[0, 100]
 *
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            int[] a = new int[n];
            String[] numStrs = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(numStrs[i]);
            }

            long res = 0;
            for (int i = 0; i <= 100; i++) {
                int realMin = Integer.MAX_VALUE; //真正的区间最小值
                long sum = 0;
                for (int j = 0; j < n; j++) {
                    if (a[j] >= i) {
                        sum += a[j];
                        realMin = Math.min(realMin, a[j]);
                    }else {
                        res = Math.max(res, realMin * sum);
                        sum = 0;
                        realMin = Integer.MAX_VALUE;
                    }
                }
                res = Math.max(res, realMin * sum);
            }
            System.out.println(res);
        }
    }
}

/*
单调栈：AC 100%，时间复杂度O(n)
栈：记录当前的最小值和对应这一区间累积和
对于第i个数，判断其与栈顶元素的大小关系：
  a. 如果比栈顶元素大，累积和=元素值，压栈
  b. 否则，栈中元素不断出栈，并计算栈元素*以此元素为最小值的最大累计和，直到栈空或满足a条件
对于得到的单调栈，再用b中的策略处理一次即可。
*/

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

struct prs {
    int val;
    int acc;
};

using namespace std;
int main()
{
    int n;
    cin>>n;
    
    stack<prs> s1;
    prs ptmp;
    int maxval = 0, tmp = 0;
    
    for(int i = 0; i < n; i++) {
        cin>>ptmp.val;
        ptmp.acc = ptmp.val;
        if(i != 0 && ptmp.val <= s1.top().val) {
            tmp = 0;
            while(!s1.empty() && ptmp.val <= s1.top().val) {
                tmp = tmp + s1.top().acc;
                maxval = max(maxval, tmp*s1.top().val);
                s1.pop();
            }
            ptmp.acc = ptmp.acc + tmp;
        }
        s1.push(ptmp);
    }
    
    tmp = 0;
    while(!s1.empty()) {
        tmp = tmp + s1.top().acc;
        maxval = max(maxval, tmp*s1.top().val);
        s1.pop();
    }
    cout<<maxval<<endl;
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,num[500001],sum=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
        sum+=num[i];
    }
    sort(num,num+n);
    cout<<sum*num[0]<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int a[n+1], s[n+1];
    memset(a, 0, sizeof(a));
    memset(s, 0, sizeof(s));
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    }
    int Max = a[1]*a[1], t, k;
    vector<int> S = {1};
    for(int i=2;i<=n;i++){
        t = S.back();
        while(a[t] >= a[i]){
            k = (S.size()>=2 ? S[S.size()-2] : 0);
            Max = max(Max, a[t]*(s[i-1]-s[k]));
            S.pop_back();
            if(S.empty())
                break;
            else
                t = S.back();
        }
        if(S.empty())
            Max = max(Max, a[i]*s[i]);
        else
            Max = max(Max, a[i]*(s[i]-s[t]));
        S.push_back(i);
    }
    while(!S.empty()){
        t = S.back();
        k = (S.size()>=2 ? S[S.size()-2] : 0);
        Max = max(Max, a[t]*(s[n]-s[k]));
        S.pop_back();
    }
    printf("%d\n", Max);
    return 0;
}

import java.util.*;

public class Main {
    /*
   public static void main(String[] args) {
        
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       int i = 0;
       int[] input = new int[n];
       while (i < n) {
            int num = scanner.nextInt();
           input[i] = num;
           ++i;
       }
       int max = 0;
       for (int index = 0; index < n; ++index) {
           int sum = input[index];
           i = index - 1;
           while (i >= 0 && input[i] >= input[index]) {
               sum += input[i];
               --i;
           }
           i = index + 1;
           while (i < n && input[i] >= input[index]) {
               sum += input[i];
               ++i;
           }
           max = Math.max(max, sum * input[index]);
       }
        System.out.println(max);
    }
    */
    private static int proc(int[] input, int begin, int end) {
        if (end == begin) {
            return 0;
        }
        if (end - begin == 1) {
            return input[begin] * input[begin];          
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = begin; i < end; ++i) {
            if (input[i] < min) {
                index = i;
                min = input[i];
            }
            sum += input[i];
        }
        //分治时左右区间必须不含中间值，如(7,2,1,4,5)通过1划分为(7,2)和（1,4,5）,(1,4,5)这个右侧区间将无法继续划分，陷入死循环
        return Math.max(sum * min, Math.max(proc(input, begin, index), proc(input, index + 1, end)));
    }
    
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int i = 0;
        int[] input = new int[n];
        while (i < n) {
            int num = scanner.nextInt();
            input[i] = num;
            ++i;
        }
        System.out.println(proc(input, 0, n));
    }
}

• 输入输出好不习惯啊

  public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
  
        int res = 0;
        for(int i=0;i<n;i++) {
            int left = i-1;
            int right = i+1;
            int sum = arr[i];
            while(left>=0 && arr[left]>=arr[i]) {
                sum+=arr[left];
                left--;
            }
            while(right<n && arr[right]>=arr[i]) {
                sum += arr[right];
                right++;
            }
            res = Math.max(res, sum*arr[i]);
        }
        System.out.println(res);
    }
  }

import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException{
		
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		int arr[]=new int[500001];
		int max=0;
		
		for(int i=0;i<N;i++) {
			arr[i]=in.nextInt();
		}
		
		for(int i=0;i<N;i++) {
			//左
			int ans=0;
			for(int j=i;j>=0;j--) {
				if(arr[i]<=arr[j]) {
					ans+=arr[j];
				}else break;
			}
			
			//右
			for(int j=i+1;j<N;j++) {
				if(arr[i]<=arr[j]) {
					ans+=arr[j];
				}else break;
			}
			max=Math.max(max, (ans*arr[i]));
			
		}
		
		System.out.println(max);
		
			
			
		}
	
		
	
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<set>
#define N 100005
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int>v(n);
	set<int>s;
	for (int i = 0; i < n; i++)cin >> v[i], s.insert(v[i]);
	long long ans = 0;
	for (int c: s)//遍历数据中的所有不同数
	{
		int cur = 0, _max = -12456789;
		for (int i = 0; i < n; i++)//遍历数组，寻找以c为最小值的区间，_max记录区间内数字和的最大值
		{
			if (v[i] >= c)cur += v[i], _max = max(_max, cur);
			else cur = 0;
		}
		ans = ans > _max*c ? ans : _max*c;
	}
	cout << ans << endl;

}

参考楼上思想，c++实现版