0 Giới thiệu

Đề bài: HZ thỉnh thoảng sẽ sử dụng các câu hỏi chuyên môn để đánh lừa những sinh viên không học ngành máy tính. Hôm nay sau khi cuộc họp của nhóm kiểm thử kết thúc, anh ấy lại nói: Trong nhận dạng mẫu một chiều cổ điển, thường xuyên cần tính toán tổng lớn nhất của vectơ con liên tục. Khi tất cả các phần tử đều là số dương, vấn đề rất dễ giải quyết. Tuy nhiên, nếu vectơ chứa số âm, có nên bao gồm một số âm nào đó và hy vọng rằng các số dương bên cạnh sẽ bù đắp cho nó không? Ví dụ: {6,-3,-2,7,-15,1,2,2}, tổng lớn nhất của vectơ con liên tục là 8 (tính từ vị trí thứ 0 đến vị trí thứ 3). Cho một mảng, hãy trả về tổng lớn nhất của dãy con liên tục, bạn có bị đánh lừa không? (độ dài của vectơ con ít nhất là 1)

1 Thiết lập ví dụ/các trường hợp kiểm thử

(1) Trường hợp toàn là số không âm:

{9, 3, 6, 8, 0, 1, 2, 4}

Cộng tất cả lại sẽ được tổng lớn nhất, tức là toàn bộ dãy chính là dãy có tổng lớn nhất

(2) Trường hợp toàn là số không dương:

{-1, -13, -9, -2, -7, 0, -4}

Một số nhỏ nhất nào đó chính là dãy con liên tục có tổng lớn nhất

(3) Trường hợp có cả số dương, số âm và số 0:

{9, 3, -1, -13, 6, 8, 0, -9, -2, -7, 1, 2, 4}

1) Chia dãy thành các dãy con khác nhau, tiêu chí chia là sự thay đổi dấu hiệu (từ "+/0" sang "-" hoặc từ "-/0" sang "+"), chuyển hóa thành

{12, -14, 14, -18, 7}

2) Liệt kê tất cả các dãy có thể bắt đầu từ số 0 hoặc số dương, kết thúc bằng số 0 hoặc số dương, cuối cùng tìm ra một dãy lớn nhất, đó chính là dãy cần tìm.

1. 12, tổng = 12

2. 12->-14->14, tổng = 12

3. 12->-14->14->-18->7, tổng = 1

4. 14, tổng = 14

5. 14->-18->7, tổng = 3

6. 7, tổng = 7

7. So sánh, kết luận dãy con liên tục có tổng lớn nhất là 14

2 Phân tích trừu tượng từ ví dụ cụ thể

Qua phân tích ở mục 1, có thể thấy thuật toán nên thực hiện theo hai bước sau:

(1) Thực hiện hợp nhất cục bộ cho toàn bộ dãy, sử dụng không gian phụ để lưu trữ dãy đã hợp nhất vector<int> myArray, dãy thu được có đặc điểm:

1. Không chứa số 0;

2. Xen kẽ chẵn lẻ;

(2) Với điều kiện giá trị bắt đầu và kết thúc >=0, tính toán tất cả các tổng dãy có thể

(3) Nếu tất cả các giá trị đều nhỏ hơn hoặc bằng 0, chỉ cần trả về số lớn nhất trong toàn bộ dãy

3 Demo

Viết một phiên bản mã rất thô sơ, may mắn vượt qua kiểm thử, ngày mai sẽ tối ưu lại, trước tiên dán ra đây

int timTongLonNhatDanhCon(vector<int> mang) {
    // Kiểm tra xem dãy có rỗng hay không
    if(mang.empty())
        return 0;
    // Kiểm tra xem dãy có tồn tại số dương không, nếu không tồn tại, chỉ cần trả về số nhỏ nhất
    int tongLonNhat = mang[0];
    for(int i=1; i<mang.size(); i++){
        if(mang[i]>tongLonNhat)
            tongLonNhat = mang[i];
    }
    if(tongLonNhat <= 0)
        return tongLonNhat;
    // Nếu tồn tại số dương
    // 1. Hợp nhất cục bộ, tách riêng số dương, số âm và số 0, đồng thời không thêm số 0 vào dãy
    vector<int> mangMoi;
    for(int i=0; i<mang.size();){
        int tong = 0;
        int coHieu;
        if(mang[i] == 0)
            coHieu = 0;
        else
            coHieu = 1;
        int j = i;
        for(; j<mang.size(); j++){
            // Số đầu tiên của dãy con là 0, duyệt qua nhưng không thêm vào hàng đợi
            if(coHieu == 0){
                if(mang[j] == 0)
                    continue;
                else{
                    i = j;
                    break;
                }
            }
            else{
                if(mang[j]*mang[i] >= 0)
                    tong += mang[j];
                if(mang[j]*mang[i]<0){
                    i = j;
                    mangMoi.push_back(tong);
                    break;
                }
            }
        }
        if(j == mang.size()){
            i = mang.size();
            mangMoi.push_back(tong);
        }
    }
    // 2. Duyệt để tìm tổng lớn nhất của dãy con liên tục
    // Khởi tạo tongLonNhat
    int viTriBatDau;
    for(int i=0; i<mangMoi.size(); i++){
        if(mangMoi[i]>0){
            viTriBatDau = i;
            tongLonNhat = mangMoi[i];
            break;
        }
    }
    for(int i=viTriBatDau; i<mangMoi.size(); i += 2){
        int viTriCon = i;
        for(int j = viTriCon + 2; j<mangMoi.size(); j += 2){
            int tongHienTai = mangMoi[viTriCon];
            for(int k = viTriCon + 1; k<= j; k++)
                tongHienTai += mangMoi[k];
            if(tongHienTai > tongLonNhat)
                tongLonNhat = tongHienTai;
        }
    }
    return tongLonNhat;
}

4 Tối ưu

Mã rõ ràng có nhiều điểm cần cải thiện, bản thân ý tưởng không rõ ràng, huống chi kỹ năng viết mã cũng không tốt, cấu trúc lộn xộn, nhìn thật sự vất vả... Tham khảo mã của người dùng mạng và cuốn "Giải pháp phỏng vấn lập trình", thực hiện điều chỉnh sau cho thuật toán.

(1) Không hợp nhất dãy nữa, chuyển sang phương pháp duyệt một lần, giảm độ phức tạp thuật toán từ O((n/2)^2) xuống O(n);

(2) Trọng tâm của việc duyệt một lần nằm ở hai biến: tổng nhỏ nhất của dãy con hiện tại currentSum và maxSum. Khi currentSum <= 0, bỏ qua currentSum hiện tại, lý do là tổng của tổng hiện tại cộng với số đang truy cập chắc chắn nhỏ hơn số đang truy cập. Lúc này, nên gán giá trị của số đang truy cập cho currentSum, bắt đầu lại từ số đó để tìm tổng lớn nhất.

(3) Khi currentSum > maxSum, cập nhật giá trị đó.

Demo như sau:

int timTongLonNhatDanhCon(vector<int> mang){
    if(mang.empty())
        return 0;
    int tongHienTai = mang[0];
    int tongLonNhat = mang[0];
    for(int i=1; i<mang.size(); i++){
        if(tongHienTai <= 0)
            tongHienTai = mang[i];
        else
            tongHienTai += mang[i];
        if(tongHienTai > tongLonNhat)
            tongLonNhat = tongHienTai;
    }
    return tongLonNhat;
}

Sau khi điều chỉnh ý tưởng, viết hoàn chỉnh đoạn mã chỉ mất khoảng mười phút, so với cách nghĩ trước đó mất khoảng một tiếng rưỡi, lần này thực sự nhanh hơn rất nhiều... Vì vậy ý tưởng viết mã mới là yếu tố quyết định.