解题思路:从三角形的最后一行倒着往上计算,以题目中给出的测试数据为例,A[4][1]的值是比较2+4和2+5得到的,显然答案是7,将7存储在本来4的位置,因为这个4以后也不会再用到了,这样就只需要一个一维的数组来存储临时的最大值就可以了。
注意事项:
参考代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t > 0) { int n = in.nextInt(); int[][] A = new int[n+1][n+1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { A[i][j] = in.nextInt(); } } int[] maxSum = new int[n+1]; for(int i = 1; i <= n; i++) { maxSum[i] = A[n][i]; } for(int i = n-1; i >= 1; i--) { for(int j = 1; j <= i; j++) { maxSum[j] = Math.max(maxSum[j], maxSum[j+1]) + A[i][j]; } } System.out.println(maxSum[1]); t--; } in.close(); } }
0.0分
0 人评分