ค่าส่วนสูงสุดหลังวางจุดแบ่ง k จุดในตัวเลขใน C++

บทนำ

ในปัญหานี้ เราได้รับสตริงที่แทนตัวเลขขนาดใหญ่และจำนวนเต็ม k ที่แทนจำนวนจุดแบ่ง (breakpoints) ภารกิจคือสร้างโปรแกรมหาค่าส่วน (Segment) สูงสุดหลังจากวางจุดแบ่ง k จุดในตัวเลข

ที่นี่เราต้องหาตัวเลขสูงสุดที่สามารถสร้างได้หลังจากวางจุดแบ่ง k จุดในตัวเลขที่กำหนดโดยสตริง

ตัวอย่าง

อินพุต - string = "45972", k = 3

เอาต์พุต - 97

คำอธิบาย -

ตัวเลขที่เป็นไปได้ทั้งหมด:
45  9  7  2
4  59  7  2
4  5  97  2
4  5  9  72
จากทั้งหมด 97 คือตัวเลขที่ใหญ่ที่สุด

เพื่อแก้ปัญหานี้ เราจะใช้เทคนิค Sliding Window ขนาดหน้าต่างจะเท่ากับ (ความยาวสตริง - k) นั่นคือตัวเลขสูงสุดจะมีขนาดนี้ เราจะตรวจสอบหาตัวเลขสูงสุดจากตัวเลขที่เป็นไปได้ทั้งหมดขนาดนี้โดยใช้ Sliding Window

ตัวอย่างโปรแกรม

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

int findMaxSegmentWithKbreaks(string &s, int k) {
    int window = s.length() - k;
    int MaxNumber = 0;
    for (int i = 0; i < window; i++)
        MaxNumber = MaxNumber * 10 + (s[i] - '0');
    int slWindow = pow(10, window - 1);
    int value = MaxNumber;
    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;
}

ผลลัพธ์

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

คำอธิบาย

ขนาดหน้าต่าง (Window Size) = n - k โดยที่ n คือความยาวสตริง สำหรับ "45972" (n=5) และ k=3 → window = 2

โปรแกรมคำนวณค่าตัวเลข 2 หลักแรก (45) แล้วเลื่อนหน้าต่างทีละ 1 ตำแหน่ง โดยลบตัวเลขหลักสิบเก่าออกและเพิ่มตัวเลขหลักหน่วยใหม่เข้าไป คำนวณค่าสูงสุดตลอดการเลื่อน