腾讯笔试第4题期末总结 不知道错哪了
思路是用两个2维数组，一个sum[i][j]保存从i到j的和，一个min[i][j]保存从i到j的最小值，只过了20%，也没提示超时(虽然是O(n^2))，大佬们看看错哪了:
#腾讯##笔试题目#
import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
helper();
}
private static void helper() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++) {
a[i] = sc.nextInt();
}
int[][] sum = new int[n+1][n+1];
int[][] min = new int[n+1][n+1];
int res = Integer.MIN_VALUE;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i == j) {
sum[i][j] = a[i-1];
min[i][j] = a[i-1];
}else if(i > j) {
continue;
}else {
sum[i][j] = sum[i][j-1] + a[j-1];
min[i][j] = min[i][j-1] < a[j-1] ? min[i][j-1] : a[j-1];
}
if(min[i][j] * sum[i][j] > res) {
res = min[i][j] * sum[i][j];
}
}
}
System.out.println(res);
}
}
#腾讯##笔试题目#
