05 August 2008
最佳观景点，给个整数数组，给个规则来计算两个pair点之间的观景得分最高
朴素DP，会超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
// dp[i] - 到i位置时的最大分数
// dp[i] = max(dp[i - 1], for (0..i - 1, j))
public int maxScoreSightseeingPair(int[] values) {
int result = 0;
if (values == null || values.length == 0) {
return result;
}
int len = values.length;
int[] dp = new int[len];
for (int j = 1; j < len; j++) {
for (int i = j - 1; i >= 0; i--) {
dp[j] = Math.max(dp[j], values[j] + values[i] + i - j);
}
result = Math.max(result, dp[j]);
}
return result;
}
}
优化时间，减少重复计算 在values[i]+i+values[j]-j中 当j固定，values[j] - j是固定值 而i从0 .. j-1中，只有最大值是有用的 每次j++后此时j=j+1，从后往前找它最好的组合i，并不需要从0..j中重新计算max values[i]+i，只需要比较当前max(由0 - j - 1算出来的)与values[j]+j进行比较 就能求出当j+1为结尾时，公式能算出的最大值 返回这个过程计算出来的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
// dp[i] - 到i位置时的最大分数
// dp[i] = max(dp[i - 1], for (0..i - 1, j))
public int maxScoreSightseeingPair(int[] values) {
int result = 0;
if (values == null || values.length == 0) {
return result;
}
int len = values.length;
//int[] dp = new int[len];
int max = values[0] + 0;
for (int j = 1; j < len; j++) {
result = Math.max(result, max + values[j] - j);
max = Math.max(max, values[j] + j);
}
return result;
}
}