- 给定一个数组arr，从左到右表示昨天从早到晚股票的价格。作为一个事后诸葛亮，你想知道如果只做一次交易，且每次交易只买卖一股，返回能挣到的最大钱数
/**
* 给定一个数组arr，从左到右表示昨天从早到晚股票的价格。作为一个事后诸葛亮，
* 你想知道如果只做一次交易，且每次交易只买卖一股，返回能挣到的最大钱数
*/
public class BuyStock01 {
public static int buyStock(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
// 每次来到i位置都都是一个卖出时机，在0~中找一个最小值点买入，i点卖出，
// 每个位置都这样操作，答案比在其中
int min = arr[0];
int res = 0;
for (int i = 0; i < arr.length; i++) {
// 更新0~i的最小值
min = Math.min(min,arr[i]);
res = Math.max(res,arr[i] - min);
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{1,2,4,3,5,6,7,8,9};
System.out.println(buyStock(arr));
}
}
- 给定一个数组arr，从左到右表示昨天从早到晚股票的价格,作为一个事后诸葛亮，你想知道如果随便交易，且每次交易只买卖一股，返回能挣到的最大钱数。
/**
* 给定一个数组arr，从左到右表示昨天从早到晚股票的价格,作为一个事后诸葛亮，
* 你想知道如果随便交易，且每次交易只买卖一股，返回能挣到的最大钱数。
*/
public class BuyStock02 {
public static int buyStock(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int money = 0;
int pre = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i] > pre){
money += arr[i] - pre;
}
pre = arr[i];
}
return money;
}
public static void main(String[] args) {
int[] arr = new int[]{1,2,4,3,5,7,6,9,8,10};
System.out.println(buyStock(arr));
}
}
- 给定一个数组arr，从左到右表示昨天从早到晚股票的价格
- 作为一个事后诸葛亮，你想知 道如果交易次数不超过K次，
- 且每次交易只买卖一股，返回能挣到的最大钱数
/**
*给定一个数组arr，从左到右表示昨天从早到晚股票的价格
* * 作为一个事后诸葛亮，你想知 道如果交易次数不超过K次，
* * 且每次交易只买卖一股，返回能挣到的最大钱数
*/
public class BuyStock03 {
public static int buyStock(int[] arr,int k){
if(arr == null || arr.length == 0 || k < 2){
return 0;
}
if(k > arr.length / 2){
return buyStock(arr);
}
int[][] dp = new int[arr.length][k+1];
// 第一行全部是0，第一列全部是0
// 求普遍位置dp[i][j]的值(含义0~i时间点随便交易，不超过j此的情况下最大钱数)
// 1)、最后的交易不在i位置，那么dp[i][j] = dp[i-1][j]
// 2)、最后的交易在i位置，且小贪心，i位置进行卖出操作，能取得最大值
// a.dp[i][j] = dp[i][j-1] + arr[i] - arr[i] ,0~i上随便交易，不超过j-1此的情况下，最后一次在i位置买，i位置卖
// b.dp[i][j] = dp[i-1][j-1] + arr[i] - arr[i-1]
// c.dp[i][j] = dp[i-2][j-1] + arr[i] = arr[i-2]
// ...
// 可以推出 max{
// dp[i][j] = dp[i][j-1] - arr[i],
// dp[i][j] = dp[i-1][j-1] - arr[i-1],
// dp[i][j] = dp[i-2][j-1] - arr[i-2],
// ....
// } + arr[i]
// 其实dp[i+1][j] = max{dp[i][j],max{dp[i+1][j-1] + arr[i+1] - arr[i+1],dp[i][j-1]-arr[i],...}+arr[i+1]}
int res = 0;
for (int j = 1; j <= k; j++) {
// dp[0][j] = dp[0][j-1] - arr[0] + arr[0]
int t = dp[0][j-1] - arr[0];
for (int i = 1; i < arr.length; i++) {
// max{dp[1][j] = dp[0][j] ,max{ dp[1][j-1] - arr[1],dp[0][j-1] - arr[0]}+arr[1]}
t = Math.max(t,dp[i][j-1]-arr[i]);
dp[i][j] = Math.max(dp[i-1][j],t+arr[i]);
res = Math.max(dp[i][j],res);
}
}
return res;
}
private static int buyStock(int[] arr){
int money = 0;
for (int i = 1; i < arr.length; i++) {
money += Math.max(arr[i] - arr[i-1],0);
}
return money;
}
}
- 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
【例子】
S = "rabbbit", T = "rabbit"
返回: 3
是以下三个S的不同子序列，没有^的位置表示删除的位置，因为删除的位置不同，所以这三 个子序列是不一样的
rabbbit
I I I I II
rabbbit
I I I I II
rabbbit
I I I I II
/**
* 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个?
* 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
* 【例子】
* S = "rabbbit", T = "rabbit"
* 返回: 3
* 是以下三个S的不同子序列，没有^的位置表示删除的位置，因为删除的位置不同，所以这三 个子序列是不一样的
* rabbbit
* I I I I II
* rabbbit
* I I I I II
* rabbbit
* I I I I II
*/
public class MaxSubSeqNum {
public static int maxSubSeqNum(String s,String t){
if((s == null && t == null) || ("".equals(s) && "".equals(t))){
return 1;
}
if((s == null && t != null) || s.length() < t.length()){
return 0;
}
// 定义dp[i][j] : s -> (0 ~ i) 子序列 随意删除 变换到，t -> (0 ~ j)的方法数
// 第一行：s中第一个位置的字符随意删除，变成t中以0~j的字符，只有第一个位置如果相等有一种
// 不相等0种，其余第一行位置全为0
// 第一列，s中取0~i的字符，j中取第一个位置的字符有几种方法变到t,如果i位置和j位置相等
// 加一种，如果i位置和j位置不相等，保留前面的种数。
// 普遍位置：
// 1.0~i随便删除，变为0~j但是不以i位置结尾 -> dp[i][j] = dp[i-1][j]
// 2.0~i随便删除 且必须以i位置结尾(有条件i位置字符等于j位置字符才有这种可能) ->dp[i][j] = dp[i-1][j-1]
// 大的过滤 s 字符的长度必须大于等于 t字符的长度，也就是说 右上半部分除了对角线都无效
char[] sA = s.toCharArray();
char[] tA = t.toCharArray();
int[][] dp = new int[s.length()][t.length()];
dp[0][0] = sA[0] == tA[0] ? 1 : 0;
// dp[0][j] 其他不用填默认0
// 列
for (int i = 1; i < sA.length; i++) {
dp[i][0] = sA[i] == tA[0] ? dp[i-1][0] + 1 : dp[i-1][0];
}
// 普遍位置(可优化，右上半部分可以不要)
for (int i = 1; i < sA.length; i++) {
for (int j = 1; j < tA.length; j++) {
dp[i][j] = dp[i-1][j] + (sA[i] == tA[j] ? dp[i-1][j-1] : 0);
}
}
return dp[sA.length-1][tA.length-1];
}
public static void main(String[] args) {
String s = "abcvcabc";
String t = "abc";
System.out.println(maxSubSeqNum(s,t));
}
}
