Giá trị đoạn lớn nhất sau khi đặt k điểm ngắt trong số C++

Cho một chuỗi biểu diễn số lớn và số nguyên k (số điểm ngắt). Tìm giá trị đoạn lớn nhất có thể tạo ra sau khi đặt k điểm ngắt.

Ví dụ

Input: string = "45972", k = 3 → Output: 97

Giải thích: Với 3 điểm ngắt, số bị chia thành 4 đoạn. Kích thước đoạn lớn nhất = 5 - 3 = 2 chữ số. Các đoạn có thể: 45, 59, 97, 72. Max = 97.

Thuật toán cửa sổ trượt

Kích thước cửa sổ = độ dài chuỗi - k. Duyệt cửa sổ qua chuỗi, tính giá trị số của mỗi cửa sổ, lấy max.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int findMaxSegmentWithKbreaks(string &s, int k) {
    int window = s.length() - k;
    int MaxNumber = 0;
    // Khởi tạo cửa sổ đầu
    for (int i = 0; i < window; i++)
        MaxNumber = MaxNumber * 10 + (s[i] - '0');
    int slWindow = pow(10, window - 1);
    int value = MaxNumber;
    // Trượt cửa sổ
    for (int i = 1; i <= (s.length() - window); i++) {
        value = value - (s[i-1] - '0') * slWindow;
        value = value * 10 + (s[i + window - 1] - '0');
        MaxNumber = max(MaxNumber, value);
    }
    return MaxNumber;
}

int main() {
    string s = "45972";
    int k = 3;
    cout << "Maximum segment value after putting " << k 
         << " break points in a number = " << findMaxSegmentWithKbreaks(s, k);
    return 0;
}

Kết quả

Maximum segment value after putting 3 breakpoints in a number = 97

Độ phức tạp: O(n) thời gian, O(1) không gian. Cửa sổ trượt cập nhật giá trị O(1) mỗi bước.