科科科
1.题目
2.分析
转移方程：前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
3.代码
class Solution {
public int maxProfit(int[] prices
) {
if(prices
.length
==0||prices
.length
==1)
return 0;
int res
=0;
int min
=Integer
.MAX_VALUE
;
for(int i
=0;i
<prices
.length
;i
++){
res
=Math
.max(res
,prices
[i
]-min
);
min
=Math
.min(min
,prices
[i
]);
}
return res
;
}
}
4.复杂度
时间复杂度 O(N) ： 其中 N 为 prices列表长度，动态规划需遍历 prices。 空间复杂度 O(1) ： 变量 用常数大小的额外空间。
5.结果
