[122. 买卖股票的最佳时机 II]
给定一个数组，它的第 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。
提示：
1 <= prices.length <= 3 * 10 ^ 40 <= prices[i] <= 10 ^ 4
贪心算法
class Solution {
public int maxProfit(int[] prices
) {
int maxProfit
= 0;
for(int i
=1;i
<prices
.length
;i
++){
if(prices
[i
]>prices
[i
-1])
maxProfit
+= prices
[i
]-prices
[i
-1];
}
return maxProfit
;
}
}
动态规划
public class Solution {
public int maxProfit(int[] prices
) {
int len
= prices
.length
;
if (len
< 2) {
return 0;
}
int cash
= 0;
int hold
= -prices
[0];
int preCash
= cash
;
int preHold
= hold
;
for (int i
= 1; i
< len
; i
++) {
cash
= Math
.max(preCash
, preHold
+ prices
[i
]);
hold
= Math
.max(preHold
, preCash
- prices
[i
]);
preCash
= cash
;
preHold
= hold
;
}
return cash
;
}
}
[300. 最长上升子序列]
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解题思路 贪心 + 二分查找 或 动态规划
class Solution {
public int lengthOfLIS(int[] nums
) {
int[] tails
= new int[nums
.length
];
int res
= 0;
for(int num
:nums
){
int i
=0,j
=res
;
while(i
<j
){
int m
= (i
+j
)/2;
if(tails
[m
]<num
) i
=m
+1;
else j
= m
;
}
tails
[i
]=num
;
if(res
==j
) res
++;
}
return res
;
}
}
动态规划
class Solution {
public int lengthOfLIS(int[] nums
) {
if(nums
.length
==0) return 0;
int[] dp
= new int[nums
.length
];
int res
= 0;
Arrays
.fill(dp
,1);
for(int i
=0;i
<nums
.length
;i
++){
for(int j
=0;j
<i
;j
++){
if(nums
[j
]<nums
[i
]) dp
[i
]=Math
.max(dp
[i
],dp
[j
]+1);
}
res
= Math
.max(res
,dp
[i
]);
}
return res
;
}
}
435无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
贪心算法
class Solution {
public int eraseOverlapIntervals(int[][] intervals
) {
if(intervals
.length
==0) return 0;
Arrays
.sort(intervals
,(a
,b
)->a
[1]-b
[1]);
int count
= 1;
int x_end
=intervals
[0][1];
for(int[] interval
:intervals
){
int start
=interval
[0];
if(start
>=x_end
){
count
++;
x_end
=interval
[1];
}
}
return intervals
.length
-count
;
}
}
动态规划
class Solution {
public int eraseOverlapIntervals(int[][] intervals
) {
if(intervals
.length
==0 || intervals
[0].length
==0) return 0;
Arrays
.sort(intervals
,(a
,b
)-> a
[0]-b
[0]);
int dp
[] = new int[intervals
.length
];
dp
[0]=1;
int ans
= 1;
for(int i
=1;i
<dp
.length
;i
++){
int max
= 0;
for(int j
=i
-1;j
>=0;j
--){
if(intervals
[j
][1]-intervals
[i
][0]<=0){
max
= Math
.max(dp
[j
],max
);
}
}
dp
[i
]=max
+1;
ans
= Math
.max(ans
,dp
[i
]);
}
return intervals
.length
-ans
;
}
}
