kadane算法

What is a sub-array?

什么是子陣列？

A sub-array is basically an array's contiguous part. For example, if we have an array of integers [1,2,3] so the sub-arrays that we can form from the given array are [1], [2] , [3] , [1,2] , [2,3] , [1,2,3].

子數組基本上是數組的連續部分。 例如，如果我們有一個整數數組[1,2,3]，那么我們可以從給定數組形成的子數組為[1]，[2]，[3]，[1,2]，[ 2,3]，[1,2,3] 。

So in the above example the sum of all the respective sub-arrays are 1,2,3,3,5,6. So here in this problem, we are required to find the maximum sub-array sum that could be obtained from a sequence of integers, which is 6 in the above case.

因此，在上面的示例中，所有各個子數組的總和為1,2,3,3,5,6 。 因此，在此問題中，我們需要找到可以從整數序列獲得的最大子數組和，在上述情況下為6 。

So many algorithms could be opted to solve the above problem, for example, a simple brute-force algorithm can be → that we can simply compute the sum of all the sub-arrays then loop through all those sums to compute maximum of those, but this algorithm will take O(N*N*N) time or in the best case O(N*N) if we try to do some pre-computation by making a cumulative some array also called a prefix sum array.

可以選擇很多算法來解決上述問題，例如，可以使用簡單的蠻力算法→這樣我們就可以簡單地計算所有子數組的總和，然后循環遍歷所有這些總和以計算出這些總和的最大值。如果我們嘗試通過使累積的某個數組也稱為前綴和數組來進行一些預計算，則此算法將花費O(N * N * N)時間，或者在最佳情況下為O(N * N) 。

So now why should we prefer KADANES's ALGORITHM?

那么，現在為什么我們應該選擇KADANES的算法 ？

It is because this algorithm can solve our problem in O(N) time that is we can obtain the maximum sub-array sum in linear time complexity which is the most optimal solution for our task.

因為該算法可以解決O(N)時間的問題，所以我們可以獲得線性時間復雜度的最大子數組和，這是我們任務的最佳解決方案。

So let us now quickly try to understand the Kadane's Algorithm in two simple steps.

因此，讓我們現在通過兩個簡單的步驟快速嘗試理解Kadane算法 。

KADANE算法 (KADANE's algorithm)

1. Initialize two variables named CS (current sum) and MS (max sum) with 0

   用0初始化兩個名為CS(當前和)和MS(最大和)的變量。

2. Loop for each element of the array and do these below tasks for each iteration,

   循環訪問數組的每個元素，并為每次迭代執行以下任務，

   1. CS = CS + ar[i]
   2. If(CS<0) then CS=0
   3. (C) If(MS<CS) then MS=CS

Description: So basically if we have to find the maximum sub-array sum of a given array then the most optimal solution is KADANE'S ALGORITHM, which can easily perform the desired task in linear time complexity that is it will take O(N) time.

描述：因此基本上，如果我們必須找到給定陣列的最大子陣列總和，則最佳解決方案是KADANE算法 ，該算法可以輕松地以線性時間復雜度執行所需任務，這將花費O(N)時間。

SO now let us quickly jump to the coding part!

現在讓我們快速跳轉到編碼部分！

Code:

碼：

#include <iostream>
using namespace std;
int main()
{
cout<<"Enter the size of an array: ";
int n;
cin>>n;
int ar[100],cs,ms;
ms=0;cs=0;
cout<<"Enter the array elements:"<<endl;
for(int i=0;i<n;i++)
cin>>ar[i];
for(int i=0;i<n;i++)
{
cs+=ar[i];
if(cs<0)
{
cs=0;
}
ms=max(cs,ms);
}
cout<<"The maximum subarray sum is: "<<endl;
cout<<ms;
return 0;
}

Output

輸出量

Enter the size of an array: 6
Enter the array elements:
1 2 3 -4 6 -1
The maximum subarray sum is:
8  

翻譯自: https://www.includehelp.com/algorithms/find-the-maximum-sub-array-sum-using-kadanes-algorithm.aspx

kadane算法