为什么sort by base_area呢？可不可以按A1sort然后dp呢？我试着练一下。create一
个class作为dp的内容including last X2 and current sumH
class dp {
int x2;
int sum;
}
public maxHeight(square[] s) {
sortSquareByA1(s); //sort by A1
int len = s.length;
int[][] dp = new int[len][s.len];
int result;
dp[0][0].sum = square[0].H;
dp[0][0].x2 = square[0].x2;
for(int i = 1; i < len; i++) { //add one more
if (square[i].A2 > square[i - 1].A2) {
dp[i][0].sum = dp[i - 1][0].sum + square[i].H;
} else {
dp[i][0].sum = square[i].H;
}
dp[i][0].x2 = square[i].x2;
}
for(int i = 1; i < len; i++) { //add nothing
dp[0][i].sum = dp[0][i-1].sum;
dp[0][i].x2 = dp[0][i-1].x2;
}
result = dp[0][0].sum;
for(int i = 1; i < len; i++) {
for(int j = 1; j < len - i; j++) {
if (square[i + j].A2 > dp[i - 1][j].x2) {
dp[i][j].sum = dp[i - 1][j].sum + square[i + j].H;
} else {
dp[i][j].sum = square[i + j].H;
}
dp[i][j].x2 = square[i + j].A2;
dp[i][j].sum = dp[i][j - 1].sum > dp[i][j].sum ? dp[i][j - 1].
sum : dp[i][j].sum;
dp[i][j].x2 = dp[i][j - 1].sum > dp[i][j].sum ? dp[i][j - 1].x2
}
result = dp[i][len - i - 1].sum > result ? dp[i][len - i - 1].sum :
result;
}
return result;
}
代码没有优化，不好看；
方法有点笨，还请指教。
