-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path09.js
More file actions
39 lines (35 loc) · 786 Bytes
/
Copy path09.js
File metadata and controls
39 lines (35 loc) · 786 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 53. 最大子序和 第一种方法：时间O(N^2)
/**
* @param {number[]} nums
* @return {number}
*/
/* var maxSubArray = function(nums) {
let max = nums[0];
for(let i=0;i<nums.length;i++){
let sum = 0;
for(let j=i;j<nums.length;j++){
sum+=nums[j];
if(sum>max){
max = sum;
}
}
}
return max;
}; */
// O(N)解法
var maxSubArray = function(nums) {
let maxSum,maxHere;
maxSum = maxHere = nums[0];
for(let i=1;i<nums.length;i++){
if(maxHere<=0){
maxHere = nums[i]
}else{
maxHere+=nums[i];
}
if(maxHere>maxSum){
maxSum = maxHere;
}
}
return maxSum;
};
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))