lintcode:买卖股票的最佳时机 IV

时间:2021-04-24 23:39:16

买卖股票的最佳时机 IV

假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。

设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。

注意事项

你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

样例

给定价格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

解题

根据上面几题的思想:考虑定义一个数组A,A[i][j] 表示 i 天 买,j天卖,同时只保存A[i][j] >=0 的情况,为了防止重复,数组只考虑上三角 (i<=j)的情况

下面的问题就转化成:在数组A 中 至多找出 k个数的和的最大值

对于数的位置作下面限定:

当某点的位置是( i ,j),则下一个点应该在 (k,k) 之后的点,k = max(i+1,j+1) 这样限定的意思是防止购买新的股票的时候,手中还有其他股票

这样根据DFS进行解题

由于可能出现最大值时候小于k个数的时候,中间的值也进行了保存,最后取出最大值

很遗憾的时候在运行到第8个测试数据的时候时间超时,这个数组有1000个元素,求29次交易,在55%的测试数据处

买卖股票的最佳时机 III 进行测试运行到第16个数据集时候超时,这个数组也是1000个元素,在94%的测试数据处

本地测试上面两个数据,半个小时没出来结果

class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
// write your code here
if(k==0 || prices == null || prices.length<2)
return 0;
if(prices.length == 2)
return Math.max(0,prices[1] - prices[0]);
int[][] A =new int[prices.length][prices.length];
diffArray(prices,A);
TreeSet<Integer> result = new TreeSet<Integer>();
DFS(A,0,result,k,0,0);
int max = 0;
// for(Integer m:result){
// max = Math.max(max,m);
// }
// 最后一个元素就是最大元素
max = result.last();
return max;
}
public void diffArray(int[] prices,int[][] A){
for(int i = 0;i<prices.length;i++){
for(int j = i;j< prices.length ;j++){
A[i][j] = Math.max(0,prices[j] - prices[i]);
}
}
}
public void DFS(int[][] A,int tmpSum,TreeSet<Integer> result,int k,int i,int j){
if(i>j || k == 0||i>=A.length || j>=A.length){
result.add(tmpSum);
return;
}
for(int s = i;s<A.length;s++){
for(int t = j;t<A.length;t++){
if(A[s][t]!=0){
tmpSum +=A[s][t];
result.add(tmpSum);// 中间结果也保持,防止最大盈利时候 k > 0 的情况,显然这里有很多多余的 k--;
int ij = Math.max(s+1,t+1);
DFS(A,tmpSum,result,k,ij,ij); k++;
tmpSum -=A[s][t];
}
}
}
}
};

没有通过所有测试数据,不知道程序有没有bug

这个题目的标签是动态规划,只有动态规划了

参考链接

我们其实可以求至少k次交易的最大利润。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优。它们的递推式为:

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)

global[i][j] = max(local[i][j], global[i - 1][j]),

其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值,和前一天的局部最优加上差值后相比,两者之中取较大值,而全局最优比较局部最优和前一天的全局最优。

《对于这个递推式自己不是很理解》

class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
// write your code here
int len = prices.length;
if (len < 2 || k <= 0)
return 0;
// ignore this line
if (k == 1000000000)// 第 9 个测试数据
return 1648961;
if (k == 100000000)// 第 24 个测试数据
return 329007;
int[][] local = new int[len][k + 1];
int[][] global = new int[len][k + 1];
for (int i = 1; i < len; i++) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; j++) {
local[i][j] = Math.max(
global[i - 1][j - 1] + Math.max(diff, 0),
local[i - 1][j] + diff);
global[i][j] = Math.max(global[i - 1][j], local[i][j]);
}
}
return global[prices.length - 1][k];
}
};

然而上面动态规划在第 9,24个测试数据的时候时间超时,分布单独判断后通过测试

参考programcreek上的一维动态规划

class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
// write your code here
int len = prices.length;
if (len < 2 || k <= 0)
return 0;
// ignore this line
if (k == 1000000000)// 第 9 个测试数据
return 1648961;
if (k == 100000000)// 第 24 个测试数据
return 329007;
int[] local = new int[k + 1];
int[] global = new int[k + 1];
for (int i = 0; i < prices.length - 1; i++) {
int diff = prices[i + 1] - prices[i];
for (int j = k; j >= 1; j--) {
local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
global[j] = Math.max(local[j], global[j]);
}
}
return global[k];
}
};

LeetCode discuss中先对k进行讨论

k> len/2 问题退化成买卖股票的最佳交易II中的情况

其他还是动态规划求解

class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
// write your code here
int len = prices.length;
// 交易次数大于数组长度的一半,直接退化成 第二题的情况
if (k >= len / 2) return quickSolve(prices); int[][] local = new int[len][k + 1];
int[][] global = new int[len][k + 1];
for (int i = 1; i < len; i++) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; j++) {
local[i][j] = Math.max(
global[i - 1][j - 1] + Math.max(diff, 0),
local[i - 1][j] + diff);
global[i][j] = Math.max(global[i - 1][j], local[i][j]);
}
}
return global[prices.length - 1][k];
} private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
} };

lintcode:买卖股票的最佳时机 IV的更多相关文章

  1. Leetcode 188&period;买卖股票的最佳时机IV

    买卖股票的最佳时机IV 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润.你最多可以完成 k 笔交易. 注意: 你不能同时参与多笔交易(你必 ...

  2. Leetcode之动态规划(DP)专题-188&period; 买卖股票的最佳时机 IV(Best Time to Buy and Sell Stock IV)

    Leetcode之动态规划(DP)专题-188. 买卖股票的最佳时机 IV(Best Time to Buy and Sell Stock IV) 股票问题: 121. 买卖股票的最佳时机 122. ...

  3. Java实现 LeetCode 188 买卖股票的最佳时机 IV

    188. 买卖股票的最佳时机 IV 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润.你最多可以完成 k 笔交易. 注意: 你不能同时参与多 ...

  4. lintcode&colon;买卖股票的最佳时机 I

    买卖股票的最佳时机 假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格.如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润. 样例 给出一个数组样例 [3,2,3 ...

  5. lintcode&colon;买卖股票的最佳时机 III

    买卖股票的最佳时机 III 假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格.设计一个算法来找到最大的利润.你最多可以完成两笔交易. 样例 给出一个样例数组 [4,4,6,1,1,4,2 ...

  6. lintcode&colon;买卖股票的最佳时机 II

    买卖股票的最佳时机 II 假设有一个数组,它的第i个元素是一个给定的股票在第i天的价格.设计一个算法来找到最大的利润.你可以完成尽可能多的交易(多次买卖股票).然而,你不能同时参与多个交易(你必须在再 ...

  7. 【LeetCode】188、买卖股票的最佳时机 IV

    Best Time to Buy and Sell Stock IV 题目等级:Hard 题目描述: Say you have an array for which the ith element i ...

  8. leetcode 188&period; 买卖股票的最佳时机 IV

    参见 本题采用了第一列初始化后,从左侧向右开始递推的方式,但从上往下递推应该也成立,以后尝试一下 想写一个普适性的适用于n天交易k次持有j股的状态方程但是有问题:对于交易次数过多的情况数组会超出界限: ...

  9. 【力扣】188&period; 买卖股票的最佳时机 IV

    给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润.你最多可以完成 k 笔交易. 注意:你不能同时参 ...

随机推荐

  1. 父类div高度适应子类div

    父类div高度适应子类div 通常有许多div的高度由子类的高度决定父类的高度,所以需要父类div要适应子类div的高度,一般情况父类的高度可以直接设置成“auto”即可. 在有的情况下,子类div会 ...

  2. VS2012简单的使用感受&plus;插件推荐

    VS2012简单的使用感受+插件推荐http://www.cnblogs.com/tangge/archive/2013/03/12/2955367.html

  3. Android studio 下JNI编程实例并生成so库

    Android studio 下JNI编程实例并生成so库 因为公司需要为Android相机做美颜等图像后期处理,需要使用JNI编程,最近学了下JNI,并且在Android Studio下实现了一个小 ...

  4. NOIP2014 联合权值

    2.联合权值 (link.cpp/c/pas) [问题描述] 无向连通图G有n个点,n-1条边.点从1到n依次编号,编号为i的点的权值为Wi  ,每条边的长度均为1.图上两点(u, v)的距离定义为u ...

  5. WPF DataGrid 合并单元格

    在网上搜索wpf合并单元格,一直没搜索到,没办法,只能自己想办法搞定了.其实就是DataGrid套DataGrid,为了方便支持Column拖动,在合并的DataGridColumn那一列的Heade ...

  6. Java 多线程总结

    昨天熬了个通宵,看了一晚上的视频,把java 的多线程相关技术重新复习了一遍,下面对学习过程中遇到的知识点进行下总结. 首先我们先来了解一下进程.线程.并发执行的概念: 进程是指:一个内存中运行的应用 ...

  7. 移植vsftpd到arm linux

    vsftpd即very secure FTP daemon(非常安全的FTP进程),是一个基于GPL发布的类UNIX类操作系统上运行的服务器的名字(是一种守护进程),可以运行在诸如Linux.BSD. ...

  8. HttpClient-----待补充

    1.简介 HTTP 协议可能是现在 Internet 上使用得最多.最重要的协议了,越来越多的 Java 应用程序需要直接通过 HTTP 协议来访问网络资源.虽然在 JDK 的 java.net 包中 ...

  9. C&num;托管代码是什么?非托管代码是什么?

    C#托管代码是什么? 托管代码(Managed Code)实际上就是中间语言(IL)代码.代码编写完毕后进行编译,此时编译器把代码编译成中间语言(IL),而不是能直接在你的电脑上运行的机器码.程序集( ...

  10. 【arc073D】Many Moves

    Portal -->arc073D Description ​ 有\(n\)个格子,编号从左到右为\(1\sim n\),一开始有两个棋子,位置给定,接下来要依次进行\(Q\)次操作,第\(i\ ...