三角形-题解（Java代码）用一维数组进行空间优化

解题思路:从三角形的最后一行倒着往上计算，以题目中给出的测试数据为例，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();
	}	
}