Cara menggunakan max subarray dan algoritma dalam C++

Cara menggunakan algoritma jumlah subarray maksimum dalam C++

Masalah jumlah subarray maksimum ialah masalah algoritma klasik, yang memerlukan mencari subarray berterusan dalam tatasusunan integer tertentu supaya semua subarray Jumlah elemen ialah terbesar. Masalah ini boleh diselesaikan menggunakan idea pengaturcaraan dinamik.

Penyelesaian yang mudah tetapi tidak cekap ialah mencari semua subarray yang mungkin dengan kaedah yang lengkap, mengira jumlahnya, dan kemudian mencari jumlah terbesar. Kerumitan masa kaedah ini ialah O(n^3), yang akan menjadi sangat perlahan apabila panjang tatasusunan adalah besar.

Penyelesaian yang lebih cekap adalah berdasarkan idea pengaturcaraan dinamik. Kita boleh merekodkan jumlah subarray maksimum yang berakhir dengan setiap elemen dengan mentakrifkan dp tatasusunan tambahan. dp[i] mewakili jumlah subarray terbesar yang berakhir dengan elemen ke-i. Untuk dp[i], terdapat dua situasi:

1. Jika dp[i-1] lebih besar daripada 0, maka dp[i] = dp[i-1] + arr[i]
2. Jika dp[i -1 ] adalah kurang daripada atau sama dengan 0, maka dp[i] = arr[i].

Kami mengira setiap elemen tatasusunan dp dengan merentasi keseluruhan tatasusunan, dan pada masa yang sama mengemas kini subarray dan max_sum terbesar serta subskrip mula dan tamat yang sepadan bermula dan tamat. Apabila jumlah subarray yang lebih besar ditemui, kami mengemas kini nilai yang sepadan. Akhir sekali, jumlah subarray maksimum ialah max_sum, dan subskrip permulaan subarray ialah permulaan dan subskrip berakhir adalah tamat.

Berikut ialah contoh kod untuk melaksanakan subarray maksimum dan algoritma dalam bahasa C++:

#include <iostream>
#include <vector>

using namespace std;

vector<int> maxSubarraySum(vector<int>& arr) {
    int n = arr.size();
    int dp[n];
    dp[0] = arr[0];
    int max_sum = dp[0];
    int start = 0, end = 0;

    for(int i = 1; i < n; i++) {
        if(dp[i-1] > 0)
            dp[i] = dp[i-1] + arr[i];
        else {
            dp[i] = arr[i];
            start = i;
        }
        
        if(dp[i] > max_sum) {
            max_sum = dp[i];
            end = i;
        }
    }
    
    vector<int> result;
    result.push_back(max_sum);
    result.push_back(start);
    result.push_back(end);

    return result;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> result = maxSubarraySum(arr);
    
    cout << "最大子数组和：" << result[0] << endl;
    cout << "子数组的起始下标：" << result[1] << endl;
    cout << "子数组的终止下标：" << result[2] << endl;

    return 0;
}

Jalankan kod di atas, hasil output adalah seperti berikut:

Jumlah subarray maksimum: 6
Subskrip permulaan subarray: 3
daripada subskrip Penamatan subarray: 6

Kod di atas menyelesaikan masalah jumlah subarray maksimum dengan kerumitan masa O(n) melalui idea pengaturcaraan dinamik. Algoritma ini sangat cekap apabila berurusan dengan tatasusunan yang besar.

Atas ialah kandungan terperinci Cara menggunakan max subarray dan algoritma dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!