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

Trong bài toán này, chúng ta được cung cấp một chuỗi biểu thị một số lớn và một số nguyên k biểu thị số điểm ngắt. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm giá trị phân đoạn lớn nhất sau khi đặt các điểm ngắt L vào một số.

Ở đây, chúng ta phải tìm số lượng lớn nhất có thể được tạo ra sau khi đặt k điểm ngắt vào số được cho bởi chuỗi.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào - string =“45972”, k =3

Đầu ra - 97

Giải thích -

All possible number is:
45    9    7    2
4    59    7    2
4    5    97    2
4    5    9    72
From all 97 is the largest number.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cửa sổ trượt. Ở đây, kích thước cửa sổ sẽ bằng (chiều dài của chuỗi - k) tức là số lượng tối đa sẽ có kích thước này. Chúng tôi sẽ kiểm tra dạng số tối đa tất cả các số có thể có của kích thước đã cho bằng kỹ thuật cửa sổ trượt.

Ví dụ

Chương trình tìm giá trị phân đoạn lớn nhất sau khi đặt K điểm ngắt vào một số -

#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;
}

Đầu ra

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