KadaneAlgo [最大连续子数组和之Kadane算法]
# 介绍
给定一个大小为 N 的数组 arr[] ，任务是找出 arr[] 内总和最大的连续子数组。
Kadane 算法的想法是维护一个变量 max_ending_here，它存储了结束于当前索引的最大连续子数，一个变量 max_so_far 存储了迄今为止发现的连续子数的最大总和，每当 max_ending_here 中出现一个正和值时，将其与 max_so_far 进行比较，如果它大于 max_so_far 则更新 max_so_far。
伪代码：
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
注意：上述算法只有在至少有一个正数的情况下才起作用，否则就不起作用，即如果一个数组包含所有的负数就不起作用。
遵循以下步骤来实施这一想法：
- 初始化变量 max_so_far = INT_MIN 和 max_ending_here = 0
- 运行一个 for 循环，从 0 到 N-1，对于每个索引 i。
- 将 arr [i] 添加到 max_ending_here。
- 如果 max_so_far 小于 max_ending_here，那么更新 max_so_far 到 max_ending_here。
- 如果 max_ending_here < 0，则更新 max_ending_here = 0。
- 返回 max_so_far
# 示例
如 [-2,1,-3,4,-1,2,1,-5,4] 。当想要计算某个元素之前的最大连续子数组和时，有两种情况：前面的和加上该元素、该元素本身。因此，在每次循环之中取两者的最大值并不断更新结果。
# 实现
# JavaScript
/* Kadane's algorithm is one of the most efficient ways to
* calculate the maximum contiguous subarray sum for a given array.
* Below is the implementation of kadanes's algorithm along with
* some sample test cases.
* There might be a special case in this problem if al the elements
* of the given array are negative. In such a case, the maximum negative
* value present in the array is the answer.
*
* Reference article :- https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
*/
function kadaneAlgo (array) {
let cummulativeSum = 0
let maxSum = Number.NEGATIVE_INFINITY // maxSum has the least possible value
for (let i = 0; i < array.length; i++) {
cummulativeSum = cummulativeSum + array[i]
if (maxSum < cummulativeSum) {
maxSum = cummulativeSum
} else if (cummulativeSum < 0) {
cummulativeSum = 0
}
}
return maxSum
// This function returns largest sum contiguous sum in a array
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
或者：
function kadaneAlgo(nums) {
let localMax = nums[0], max = nums[0];
for (let i=1;i<nums.length;i++) {
localMax = Math.max(nums[i], localMax + nums[i]);
max = Math.max(max, localMax);
}
return max;
};
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
如果全部是正数，则全数组是最大连续子数组。
# 参考
编辑 (opens new window)
上次更新: 2022/10/25, 20:46:09