给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列 [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;输出描述:输出数组经过计算后的最大值。输入例子1:36 2 1输出例子1:36import java.util.Scanner;import java.util.Arrays;public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n]; int sum=0; int max=0; for ( int i = 0; i < n; i++ ){ a[i]=in.nextInt(); } for(int i=0;i<n;i++){ //以某元素为最小值扩展到附近区间,使得主顺序遍历一遍就可以 sum=0; int f=i; int e=i; if(i>0){ for (int k=i-1;k>=0;k--){ if(a[k]<a[i]){ f=k+1; break; } f=0;//扩展到左边 不要忘记如果左边都大于基值 将起始位置置0 } } if(i<n-1){ for(int j=i+1;j<n;j++){ if(a[j]<a[i]){ e=j; break; //出现第一个小于基值 则退出 } e=n; } } for(int b=f;b<e;b++){ sum += a[b]; } max=Math.max(max,a[i]*sum); } System.out.println(max); }}