Thuật toán Kadence: Mảng con liền kề có tổng lớn nhất

Mảng con liền kề có tổng lớn nhất là gì?

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ụ, xét mảng {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Các mảng con của nó có thể là {-10, 5, 1, 6}, {5, 1, 6}, hoặc {2, -7, 3, -5}, v.v. Tuy nhiên, {5, 1, 6, 3} không thể là một mảng con vì các phần tử không nằm trong một dãy liên tục.

Nếu bạn để ý, trong tất cả các mảng con, mảng con được tô sáng {5, 1, 6} có tổng giá trị lớn nhất:

Tổng của mảng con {5, 1, 6} là 12, là tổng lớn nhất trong tất cả các mảng con có thể có của mảng trên. Vì vậy, đối với mảng này, mảng con liền kề có tổng lớn nhất là {5, 1, 6}.

Phương pháp đơn giản để giải bài toán tìm tổng lớn nhất trong các mảng con liền kề

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ơ đồ thuật toán cho phương pháp đơn giản tìm mảng con liền kề có tổng lớn nhất. Đây là phương pháp vét cạn, vì chúng ta sẽ duyệt qua mọi 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ổng tối đa với giá trị số nguyên tối thiểu và được thiết lập bắt đầu và cuối về không.

Bước 2) Hãy liên hệ với i và j là các chỉ số mảng trong đó j là lớn hơn hoặc bằng i; i đánh dấu điểm bắt đầu của mảng con và j Kết thúc của nó.

Bước 3) tổng hiện tại lưu giữ tổng tích lũy. Sau mỗi lần cập nhật, hãy kiểm tra xem tổng hiện tại lớn hơn tổng tối đa.

Bước 4) If tổng hiện tại lớn hơn, thay thế tổng tối đa với nó.

Bước 5) Thời Gian j Khi đạt đến cuối mảng, hãy tăng giá trị lên. i và đặt lại tổng hiện tại để 0.

Bước 6) Lặp lại cho đến khi i Đạt đến cuối mảng. tổng tối đa sau đó lưu giữ tổng mảng con lớn nhất.

Biệt danh Code Cách tiếp cận đơn giản

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 tiếp cận đơ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 phương pháp lập trình động sử dụng một vòng lặp duy nhất thay vì hai vòng lặp. Nó xử lý các mảng có chứa cả số dương và số âm, miễn là ít nhất một giá trị là không âm.

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:

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, tổng hiện tại và tổng tối đa.

tổng hiện tại giữ lại tổng lớn nhất kết thúc tại một chỉ mục mảng cụ thể, trong khi tổng tối đa Lưu trữ giá trị tổng lớn nhất đã quan sát được cho đến nay.

Bước 2) Thêm từng phần tử mảng vào tổng hiện tạiSau đó, hãy kiểm tra hai điều kiện dưới đây:

• If tổng hiện tại nhỏ hơn phần tử hiện tại thì tổng hiện tại trở thành yếu tố hiện tại.
• If tổng tối đa ít hơn tổng hiện tạithì tổng tối đa trở thành tổng hiện tại.

Bước 3) Sau khi lặp lại bước trước đó cho toàn bộ mảng, tổng tối đa Chứa mảng con liền kề có tổng lớn nhất.

Ví dụ về thuật toán Kadane

Chúng tôi sẽ trình bày thuật toán Kadane trên một mảng nhỏ và hướng dẫn từng bước tìm mảng con liền kề có tổng lớn nhất.

Giả sử mảng đã cho có dạng như sau:

Dưới đây là các bước của thuật toán Kadane:

Bước 1) Tạo hai biến, tổng hiện tại và tổng tối đaGán INT_MIN cho tổng tối đa và từ không đến tổng hiện tạiỞ đây, INT_MIN biểu thị giá trị số nguyên nhỏ nhất.

Bước 2) Tại chỉ số 0, giá trị là 4. Vì vậy, tổng hiện tại = 0 + 4 = 4. Vì tổng hiện tại lớn hơn tổng tối đa, tổng tối đa trở thành 4.

Bước 3) Tại chỉ số 1, giá trị là -2. Vì vậy, tổng hiện tại = 4 + (-2) = 2.

Thời gian này tổng hiện tại ít hơn tổng tối đaDo đó, giá trị của tổng tối đa không được cập nhật.

Bước 4) Giá trị tiếp theo là 1. Cộng nó vào tổng hiện tại cho kết quả là 3. Vì tổng tối đa (4) vẫn lớn hơn tổng hiện tại, tổng tối đa không được cập nhật.

Bước 5) Tại chỉ số 3, giá trị là 3. Tăng dần tổng hiện tại bởi 3 cho tổng hiện tại = 6.

Trong trường hợp này, tổng tối đa nhỏ hơn tổng hiện tại, Vì vậy tổng tối đa được cập nhật với giá trị của tổng hiện tại.

Bước 6) Đối với phần tử cuối cùng của mảng, ta có -1. Cộng nó vào... tổng hiện tại cho kết quả là 5, nhỏ hơn tổng tối đa. Vì thế, tổng tối đa còn lại 6.

Khi chúng ta đã đến cuối mảng, thuật toán kết thúc tại đây. Bây giờ, tổng tối đa Chứa tổng lớn nhất, là 6. Mảng con là {4, -2, 1, 3}.

Biệt danh Code Đối với thuật toán Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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

Phương pháp đơn giản sử dụng hai vòng lặp để tính toán tổng của mọi mảng con có thể và tìm tổng lớn nhất. Đây là phương pháp vét cạn; mỗi vòng lặp chạy đến cuối mảng. mảng, cho O(N²) thời gian.

Thuật toán Kadane chỉ sử dụng một vòng lặp, cho thời gian O(N) và không gian bổ sung O(1). Trên một mảng gồm 100 phần tử, phương pháp đơn giản thực hiện 100 × 100 = 10,000 phép toán, trong khi thuật toán Kadane chỉ thực hiện 100 phép toán — một sự tăng tốc đáng kể đối với các đầu vào lớn.

Câu Hỏi Thường Gặp