forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmike2ox.ts
More file actions
22 lines (19 loc) Β· 783 Bytes
/
mike2ox.ts
File metadata and controls
22 lines (19 loc) Β· 783 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* source: https://leetcode.com/problems/maximum-subarray/
* νμ΄λ°©λ²: νμ¬ μμΉκΉμ§μ μ΅λ ν©μ μ μ₯νλ©΄μ μ 체 μ΅λ ν©μ κ°±μ
* μκ°λ³΅μ‘λ: O(n) (n: numsμ κΈΈμ΄)
* 곡κ°λ³΅μ‘λ: O(1) (μμ 곡κ°λ§ μ¬μ©)
*/
function maxSubArray(nums: number[]): number {
// λ°°μ΄μ΄ λΉμ΄μλ κ²½μ°
if (nums.length === 0) return 0;
let result = nums[0]; // μ 체 μ΅λ ν©(μ΄κΈ°κ°μ 첫 λ²μ§Έ μμ)
let current = nums[0]; // νμ¬ μμΉκΉμ§μ μ΅λ ν©
for (let i = 1; i < nums.length; i++) {
// νμ¬ μμλ₯Ό λν κ°κ³Ό νμ¬ μμ μ€ ν° κ°μ μ ν
current = Math.max(nums[i], current + nums[i]);
// μ 체 μ΅λ ν© κ°±μ
result = Math.max(result, current);
}
return result;
}