roma-dxunvrs
22 lines
960 B
Markdown
22 lines
960 B
Markdown
Leetcode #53 | #Medium | [[1-D Динамика]]
|
|
## Идея
|
|
Храним текущую сумму - изначально первый элемент. Идем по массиву, начиная с 1-го индекса. Считаем текущую сумму как максимум из `nums[i]` и `nums[i]+curSum`. Если текущая сумма была отрицательной, а встретилось число, большее, то просто начинаем отсчет с него. Обновляем максимальную сумму.
|
|
## Big-O
|
|
- Время ```O(N)```
|
|
- Память ```O(1)```
|
|
## Код
|
|
```Java
|
|
class Solution {
|
|
public int maxSubArray(int[] nums) {
|
|
int curSum = nums[0];
|
|
int maxSum = curSum;
|
|
|
|
for (int i = 1; i < nums.length; i++) {
|
|
curSum = Math.max(nums[i], nums[i]+curSum);
|
|
maxSum = Math.max(maxSum, curSum);
|
|
}
|
|
|
|
return maxSum;
|
|
}
|
|
}
|
|
``` |