2022年4月4日
dp第七天
这一题使用平时的方法,两层循环的话超时,需要把公式转换一下,可以只遍历一次
/**
1014. 最佳观光组合
给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1:
输入:values = [8,1,5,2,6]
输出:11
解释:i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2:
输入:values = [1,2]
输出:2
提示:
2 <= values.length <= 5 * 10^4
1 <= values[i] <= 1000
* @author zeroheart
*
*/
public class Question1014 {
public int maxScoreSightseeingPair(int[] values) {
// int len = values.length;
// int maxIJ = 0;
// for(int i=0; i<len; i++){
// for(int j = i+1; j<len; j++){
// maxIJ = Math.max(values[i] + values[j] + i - j, maxIJ);
// }
// }
// return maxIJ;
int len = values.length;
int max = 0;
int premax = values[0]+0;
// values[i] + values[j] + i - j
// 改写成,values[i] + i + values[j] - j,对于j来说,values[i] + i 最大即可
// O(n2)->O(n)
for(int i = 1; i<len; i++){
max = Math.max(max, premax + values[i] - i);
premax = Math.max(premax, values[i] + i);
}
return max;
}
public static void main(String[] args) {
}
}
这题是简单题,用到的居然和上面是一样的,只是没有公式的转换了
/** 121. 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。 示例 1: 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。 示例 2: 输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。 提示: 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 * @author zeroheart * */ public class Question121 { public int maxProfit(int[] prices) { // pre = min, max = price - min int len = prices.length; int pre = prices[0]; int max = 0; for(int i = 1; i<len; i++){ max = Math.max(max, prices[i] - pre); pre = Math.min(pre, prices[i]); } return max; } public static void main(String[] args) { } }