目录
给定一个数组 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
解释：在这种情况下, 没有交易完成,
? ?1 使用暴力，两层for，记录最大差值
? ?2 使用贪心，从第一个递增的位置开始，求最大的sum
? ?3 卡哥要求使用dp ，但是我没想出办法
? ? ? ? 令dp为最大利润，无法判断
? ? ? ? 对于第i天的股票，有两种状态
? ? ? ? 1 买入状态
? ? ? ? ? ? ? ? 1 之前就买入
? ? ? ? ? ? ? ? 2 第i天买入
? ? ? ? 2 卖出状态
? ? ? ? ? ? ? ? 1 之前就卖出
? ? ? ? ? ? ? ? 2 第i天卖出
? ? ? ? 确定dp数组以及下标的含义
? ? ? ? int dp[i][2]
????????dp[i][0]:代表第i天持有股票的最大现金
? ? ? ? dp[i][1]:代表卖出后的值，第i天不持有股票的最大现金?
? ? ? ? 确定递推公式
? ? ? ? 若当天买入 则为 -price[i]
? ? ? ? dp[i][0] = Math.max(dp[i-1][0],0-price[i])
????????若当天卖出，则为dp[i-1][0]+price[i]
????????dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+price[i]);
? ? ? ?dp数组初始化
? ? ? ? dp[0][0]=-price[i]
? ? ? ? dp[0][1] = 0
????????确定遍历顺序
? ? ? ? 从前往后
? ? ? ? 举例推导dp数组
? ? ? ??????????
? ? ? ? 过程比较绕需要再消化一下
? ? ? ? dp的定义和赋值
class Solution {
public int maxProfit(int[] prices) {
//我的做法
//暴力，两层for求最大差值，进行返回
//贪心，从第一个前面小于后面的开始，看后面的最大差值
/*int maxDiff=0;
for(int i=0;i<prices.length-1;i++){
if(prices[i]<prices[i+1]){
int j=i+1;
while(j<prices.length&&prices[i]<=prices[j]){
int diff = prices[j]-prices[i];
maxDiff = maxDiff>diff?maxDiff:diff;
j++;
}
i=j-1;
}
}
return maxDiff;*/
//卡哥思路，统一做法二维数组
//dp数组的定义和下标的含义
//dp[i][0]第i天持有股票的现金最大值，dp[i][1]第i天不持有股票的所得最大现金
//确定递推公式
//dp[i][0] 第i天持有股票的最大现金之前和今天哪个拥有现金最大，取最大的Math.max(dp[i-1][0],-price[i]);
//dp[i][1] 第i天不持有股票的最大值，看之前卖出后和今天卖出后哪个最大
//Math.max(dp[i-1][1],dp[i-1][0]+price[i]);
//dp数组初始化
// dp[0][0] = -price[0],dp[0][1] = 0;
//确定遍历顺序
//从前往后
//举例推导dp数组
//打印dp数组
int[][] dp = new int[prices.length][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<prices.length;i++){
//之前和今天买入哪个拥有的现金最多
dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
//之前卖出和今天卖出(今天卖出的，前一天买入的留下最大现金卖出则+prices[i]，dp[i-1][0]+price[i])
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[prices.length-1][1];
}
}给定一个数组，它的第?i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例?3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
?????????使用贪心，从第一个递增的位置开始，求最大的sum
? ?????卡哥要求使用dp ，按照之前的办法没想出来
? ? ? ? 对于第i天的股票，有两种状态
? ? ? ? 1 买入状态
? ? ? ? ? ? ? ? 1 之前就买入
? ? ? ? ? ? ? ? 2 第i天买入
? ? ? ? 2 卖出状态
? ? ? ? ? ? ? ? 1 之前就卖出
? ? ? ? ? ? ? ? 2 第i天卖出
? ? ? ? 确定dp数组以及下标的含义
? ? ? ? int dp[i][2]
????????dp[i][0]:代表第i天持有股票的最大现金
? ? ? ? dp[i][1]:代表卖出后的值，第i天不持有股票的最大现金?
? ? ? ? 确定递推公式
? ? ? ? 若当天买入 则为 dp[i-1][1]-price[i],
????????若当天买入，则之前未买入，将之前未买入的现金来进行买入操作dp[i-1][1]-price[i]
? ? ? ? dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-price[i])
????????若当天卖出,则之前买入过，则为dp[i-1][0]+price[i]
????????dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+price[i]);
? ? ? ?dp数组初始化
? ? ? ? dp[0][0]=-price[0]
? ? ? ? dp[0][1] = 0
????????确定遍历顺序
? ? ? ? 从前往后
? ? ? ? 举例推导dp数组
? ? ? ??????????
? ? ? ? 过程比较绕需要再消化一下
? ? ? ? dp的定义和赋值
class Solution {
public int maxProfit(int[] prices) {
//贪心 如果后面的比前面的要大，则加上
/*int sum=0;
for(int i=0;i<prices.length-1;i++){
if(prices[i]<prices[i+1]){
sum+=(prices[i+1]-prices[i]);
}
}
return sum;*/
//确定dp数组以及每个下标的含义
//和上一题一样
//dp[i][0] 表示第i天持有股票所得现金。
//dp[i][1] 表示第i天不持有股票所得最多现金
//确定递推公式()
//第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
//第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
// 和上一题的区别，若第i天买入股票，则需要用昨天不持有股票的现金去买，dp[i-1][1]-price[i]
// 若第i天不买入股票，则取上一天的值
// 若第i天卖出股票，
// 当前是持有股票的状态，则dp[i][1] = dp[i-1][0]+price[i]
// (不用累加上一次卖出股票的现金吗?不用，这里考虑的是上一次持有股票的状态卖出后的结果)
// 若第i天不卖出股票，则dp[i][1] = dp[i-1][1]
//dp数组初始化
//dp[0][0]=-price[0],dp[0][1]=0
//确定遍历顺序
//从前往后
//举例推导dp数组
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1;i<prices.length;i++){
//当天买入,则看之前没买入dp[i-1][1]-price[0]
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
//当天卖出，则看之前买入的值
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[prices.length-1][1];
}
}