2022年4月4日 作者 zeroheart

dp第七天

1014. 最佳观光组合

这一题使用平时的方法,两层循环的话超时,需要把公式转换一下,可以只遍历一次

/**
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. 买卖股票的最佳时机

这题是简单题,用到的居然和上面是一样的,只是没有公式的转换了

/**
 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) {

    }
}