Thuật toán Kadence: Mảng con liền kề có tổng lớn nhất
Sarah Chen
Phân mảng liền kề có tổng lớn nhất là bao nhiêu?
Mảng con là một phần liên tục của mảng. Nó có thể là một phần tử của mảng hoặc một phần nào đó của mảng. Mảng con liền kề có tổng lớn nhất có nghĩa là mảng con có giá trị tổng lớn nhất.
Ví dụ: một mảng là {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Các mảng con của nó có thể là: {-10,5,1,6} hoặc {5,1,6} hoặc {2,7,3, -5}, v.v. Nhưng {5,1,6,3} không thể là một mảng con vì chúng không duy trì trình tự.
Nếu bạn để ý, trong số tất cả các mảng con, mảng con được tô sáng sau (5,1,6) có giá trị tổng lớn nhất:
Tổng của mảng con {5,1,6} = 11, là tổng lớn nhất trong tất cả các tổ hợp mảng con của mảng trên. Vì vậy, đối với mảng trên, mảng con tối đa là {5,1,6}.
Thuật toán Kadence: Mảng con liền kề có tổng lớn nhất
Cách tiếp cận đơn giản để giải mảng con liền kề có tổng lớn nhất
Cách đơn giản để giải quyết vấn đề này là sử dụng hai vòng lặp để tìm tất cả các mảng con, tính tổng rồi tìm giá trị lớn nhất của nó.
Đây là sơ đồ cho cách tiếp cận đơn giản để tìm mảng con liền kề có tổng lớn nhất. Đây là một cách tiếp cận mạnh mẽ vì chúng ta đang xem xét tất cả các mảng con có thể có.
Dưới đây là các bước đơn giản để làm điều này.
Bước 1) Khởi tạo max_sum với giá trị số nguyên tối thiểu và gán các biến “bắt đầu” và “kết thúc” bằng 0.
Bước 2) Gọi i và j là chỉ số của mảng, trong đó “j” lớn hơn “i”. Nó đại diện cho chỉ mục bắt đầu của mảng con và “j” đại diện cho chỉ mục kết thúc của mảng con.
Bước 3) “Current_sum” sẽ chứa tổng của mảng con. Sau khi tính tổng hiện tại, hãy kiểm tra xem current_sum có lớn hơn max_sum hay không.
Bước 4) Nếu current_sum lớn hơn thì thay thế max_sum bằng tổng hiện tại.
Bước 5) Kiểm tra xem “j” có đến cuối mảng hay không. Nếu “j” đến cuối mảng thì tăng “i” và thay đổi giá trị current_sum thành 0.
Bước 6) Thực hiện tất cả các bước này cho đến khi “i” đến cuối mảng.
Bước 7) Ở cuối hai vòng lặp này, max_sum sẽ giữ tổng mảng con lớn nhất.
Mã giả cho cách tiếp cận đơn giản
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
store the maximum subArray
return the maximum sum
C++ Thực hiện phương pháp tiếp cận đơn giản
#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
int max_sum = -1e9;
int begin = 0;
int end = 0;
for (int i = 0; i < n; i++) {
int current_sum = 0;
for (int j = i; j < n; j++) {
current_sum += array[j];
if (max_sum < current_sum) {
max_sum = current_sum;
begin = i;
end = j;
}
}
}
cout << "largest sum is " << max_sum << endl;
cout << "largest sum contiguous subarray: ";
for (int i = begin; i <= end; i++) {
cout << array[i] << "\t";
}
}
int main() {
int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}
Đầu ra:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Thực hiện phương pháp đơn giản
def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
for i in range(len(numbers)):
current_sum=0
for j in range(i,len(numbers)):
current_sum+=numbers[j]
if max_sum<current_sum:
max_sum=current_sum
begin,end=i,j
print("largest sum is ",max_sum)
print("largest sum contiguous subarray: ",end="")
for i in range(begin,end+1):
print(numbers[i],end='\t')
numbers = [-10,5,1,6,-9,2,-7,3,-5]
maximumSubarraySum(numbers)
Đầu ra:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Thuật toán Kadane để tìm mảng con liền kề có tổng lớn nhất
Thuật toán Kadane là một loại phương pháp “Lập trình động”. Ở đây chúng ta sẽ sử dụng một vòng lặp thay vì hai vòng lặp. Việc triển khai chung Thuật toán Kadane chỉ có tác dụng đối với mảng số dương.
Chúng ta chỉ cần hai biến để tìm mảng con liền kề có tổng lớn nhất. Đây là sơ đồ thuật toán Kadane:
Dưới đây là các bước thực hiện Thuật toán Kadane:
Bước 1) Tạo hai biến, current_sum và max_sum.
“Current_sum” sẽ giữ giá trị của tổng tối đa kết thúc bằng một chỉ mục mảng cụ thể, trong khi “max_sum” sẽ lưu trữ giá trị tổng tối đa cho đến nay.
Bước 2) Chúng ta sẽ thêm giá trị bằng current_sum cho từng phần tử mảng. Sau đó chúng ta sẽ kiểm tra hai điều kiện dưới đây:
- Nếu current_sum nhỏ hơn phần tử hiện tại thì giá trị current_sum sẽ là phần tử hiện tại.
- Nếu max_sum nhỏ hơn current_sum thì max_sum sẽ là current_sum.
Bước 3) Thực hiện bước trước cho toàn bộ mảng, chúng ta sẽ có mảng con liền kề có tổng lớn nhất trong biến “max_sum”.
Ví dụ về thuật toán Kadane
Chúng ta sẽ trình diễn Thuật toán Kadanes bằng một mảng có kích thước nhỏ và thảo luận từng bước để tìm mảng con liền kề có tổng lớn nhất.
Giả sử mảng được cho giống như sau:
Đây là các bước của Thuật toán Kadane:
Bước 1) Tạo hai biến, current_sum và max_sum. Gán INT_MIN cho max_sum và 0 cho current_sum. (Ở đây, INT_MIN có nghĩa là số nguyên tối thiểu).
Bước 2) Tại chỉ số 0, giá trị là 4. Vậy, current_sum = 0 + 4 hoặc 4. Ở đây current_sum lớn hơn max_sum, max_sum sẽ là 4.
Bước 3) Tại chỉ số 1, giá trị là -2. Vì vậy, current_sum = 4 + (-2) hoặc 2.
Lần này, current_sum nhỏ hơn max_sum. Kết quả là giá trị của max_sum sẽ không được cập nhật.
Bước 4) Giá trị tiếp theo là 1. Nếu chúng ta cộng giá trị này với current_sum thì current_sum sẽ là 3. Tuy nhiên, max_sum vẫn lớn hơn current_sum. Vì vậy, max_sum sẽ không được cập nhật.
Bước 5) Tại chỉ số 3, giá trị là ba. Chúng tôi sẽ cập nhật giá trị bằng cách tăng current_sum lên 3. Vì vậy, current_sum sẽ là 6.
Trong trường hợp này, max_sum nhỏ hơn current_sum. Vì vậy, max_sum sẽ được cập nhật với giá trị của current_sum.
Bước 6) Đối với phần tử cuối cùng của mảng, chúng ta có -1. Nếu chúng ta cộng giá trị này với current_sum thì current_sum sẽ là 5, nhỏ hơn max_sum. Vì vậy, max_sum sẽ vẫn là 6.
Khi chúng ta đến cuối mảng, thuật toán kết thúc tại đây. Bây giờ, “max_sum” chứa mảng con có tổng tối đa. Đó là 5. Mảng con là {4,-2,1,3}.
Mã giả cho thuật toán Kadane
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements in array:
add the element with current_sum
if current_sum is greater than the maximum_sum
then maximum_sum = current_sum
if current_sum is less than the element
then current_sum = element
return the value of maximum_sum
C++Triển khai thuật toán Kadane
#include < iostream >
using namespace std;
void kadane(int array[], int n) {
int current_sum = 0;
int max_sum = -1e9;
// -1e9 means -10000000
for (int i = 0; i < n; i++) {
current_sum += array[i];
if (max_sum < current_sum) {
max_sum = current_sum;
}
if (current_sum < array[i]) {
current_sum = array[i];
}
}
cout << "largest sum is " << max_sum << endl;
}
int main() {
int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
kadane(array, sizeof(array) / sizeof(array[0]));
}
Đầu ra:
largest sum is 12
Python Triển khai thuật toán Kadane
def kadane(numbers):
current_sum = 0
max_sum = -1e9
for i in range(len(numbers)):
current_sum += numbers[i]
if max_sum < current_sum:
max_sum = current_sum
if current_sum<numbers[i]:
current_sum = numbers[i]
print("largest sum is ",max_sum)
kadane([-10,5,1,6,-9,2,-7,3,-5])
Đầu ra:
largest sum is 12
Phân tích độ phức tạp cho mảng con liên tiếp tổng lớn nhất
Cách tiếp cận đơn giản sử dụng hai vòng lặp. Phương pháp đó tính toán tất cả các tổng của mảng con có thể có để tìm ra số lớn nhất. Đó là một cách tiếp cận vũ phu. Mỗi vòng lặp chạy cho đến hết mảng.
Nếu một mảng có tổng cộng N phần tử, sau đó sử dụng hai vòng lặp, chúng ta sẽ đi qua N2 các phần tử. Do đó, độ phức tạp về thời gian cho một cách tiếp cận đơn giản để tìm mảng con liên tiếp tổng lớn nhất sẽ là O(N2). Ở đây, “O” có nghĩa là hàm phức tạp.
Mặt khác, Thuật toán Kadane là phương pháp Lập trình động để tìm mảng con tổng liền kề lớn nhất. Nếu bạn làm theo ví dụ hoặc mã, bạn sẽ thấy rằng chúng tôi chỉ sử dụng một vòng lặp.
Kết quả là, nếu mảng đầu vào có kích thước là N, thì độ phức tạp thời gian của Thuật toán Kadane sẽ là O(N). Nhanh hơn phương pháp tiếp cận đơn giản. Ví dụ, một mảng chứa 100 phần tử. Phương pháp tiếp cận đơn giản sẽ mất 100*100 hoặc 10,000 thời gian CPU. Nhưng Thuật toán Kadane sẽ chỉ mất 100 thời gian CPU.
