roma-dxunvrs
25 lines
1.2 KiB
Markdown
25 lines
1.2 KiB
Markdown
Leetcode #121 | Easy | [1-D Динамика](../../Методы/1-D%20Динамика.md)
|
|
## Идея
|
|
Ставим левый указатель на 0 и идем по массиву правым. Если цена на левом меньше цены на правом, то можно зафиксировать прибыль - обновляем результат. Если же цена стала меньше либа равна, то двигаем левый указатель на место правого. Мы не может потерять никаких промежуточных сумм на этом действии, потому что в силу монотонности, никаие значения на (l,r) не удовлетворяли `p[l]<p[r]`
|
|
## Big-O
|
|
- Время ```O(N)```
|
|
- Память ```O(1)```
|
|
## Код
|
|
```Java
|
|
class Solution {
|
|
public int maxProfit(int[] prices) {
|
|
int res = 0;
|
|
int l = 0;
|
|
|
|
for (int r = 0; r < prices.length; r++) {
|
|
if (prices[l] < prices[r]) {
|
|
res = Math.max(res, prices[r]-prices[l]);
|
|
} else {
|
|
l = r;
|
|
}
|
|
}
|
|
|
|
return res;
|
|
}
|
|
}
|
|
``` |