腾讯笔试第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); } }
#腾讯##笔试题目#