Dado un número grande como string s y un entero k que denota el número de puntos de interrupción, debemos poner el número k <= longitud de string. La tarea es encontrar el valor máximo del segmento después de colocar exactamente k puntos de ruptura. Ejemplos:
Input : s = "8754", k = 2 Output : Maximum number = 87 Explanation : We need to two breakpoints. After putting the breakpoints, we get following options 8 75 4 87 5 4 The maximum segment value is 87. Input : s = "999", k = 1 Output : Maximum Segment Value = 99 Explanation : We need to one breakpoint. After putting the breakpoint, we either get 99,9 or 9,99.
Una observación importante es que el máximo siempre sería de longitud «longitud de string – k», que es el valor máximo de cualquier segmento. Teniendo en cuenta el hecho, el problema se vuelve como un problema de ventana deslizante, lo que significa que necesitamos encontrar el máximo de todas las substrings de tamaño (longitud de string – k).
C++
// CPP program to find the maximum segment
// value after putting k breaks.
#include <bits/stdc++.h>
using namespace std;
// Function to Find Maximum Number
int findMaxSegment(string &s, int k) {
// Maximum segment length
int seg_len = s.length() - k;
// Find value of first segment of seg_len
int res = 0;
for (int i=0; i<seg_len; i++)
res = res * 10 + (s[i] - '0');
// Find value of remaining segments using sliding
// window
int seg_len_pow = pow(10, seg_len-1);
int curr_val = res;
for (int i = 1; i <= (s.length() - seg_len); i++) {
// To find value of current segment, first remove
// leading digit from previous value
curr_val = curr_val - (s[i-1]- '0')*seg_len_pow;
// Then add trailing digit
curr_val = curr_val*10 + (s[i+seg_len-1]- '0');
res = max(res, curr_val);
}
return res;
}
// Driver's Function
int main() {
string s = "8754";
int k = 2;
cout << "Maximum number = " << findMaxSegment(s, k);
return 0;
}
Java
// Java program to find the maximum segment
// value after putting k breaks.
class GFG {
// Function to Find Maximum Number
static int findMaxSegment(String s, int k) {
// Maximum segment length
int seg_len = s.length() - k;
// Find value of first segment of seg_len
int res = 0;
for (int i = 0; i < seg_len; i++)
res = res * 10 + (s.charAt(i) - '0');
// Find value of remaining segments using
// sliding window
int seg_len_pow = (int)Math.pow(10,
seg_len - 1);
int curr_val = res;
for (int i = 1;
i <= (s.length() - seg_len); i++) {
// To find value of current segment,
// first remove leading digit from
// previous value
curr_val = curr_val -
(s.charAt(i - 1) - '0') * seg_len_pow;
// Then add trailing digit
curr_val = curr_val * 10 +
(s.charAt(i + seg_len - 1) - '0');
res = Math.max(res, curr_val);
}
return res;
}
// Driver code
public static void main(String[] args) {
String s = "8754";
int k = 2;
System.out.print("Maximum number = "
+ findMaxSegment(s, k));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find the maximum segment
# value after putting k breaks.
# Function to Find Maximum Number
def findMaxSegment(s, k):
# Maximum segment length
seg_len = len(s) - k
# Find value of first segment of seg_len
res = 0
for i in range(seg_len):
res = res * 10 + (ord(s[i]) - ord('0'))
# Find value of remaining segments
# using sliding window
seg_len_pow = pow(10, seg_len - 1)
curr_val = res
for i in range(1, len(s) - seg_len):
# To find value of current segment,
# first remove leading digit from
# previous value
curr_val = curr_val - (ord(s[i - 1])-
ord('0')) * seg_len_pow
# Then add trailing digit
curr_val = (curr_val * 10 +
(ord(s[i + seg_len - 1]) - ord('0')))
res = max(res, curr_val)
return res
# Driver Code
if __name__ == '__main__':
s = "8754"
k = 2
print("Maximum number = ",
findMaxSegment(s, k))
# This code is contributed by PranchalK
C#
// C# program to find the maximum segment
// value after putting k breaks.
using System;
class GFG {
// Function to Find Maximum Number
static int findMaxSegment(string s, int k) {
// Maximum segment length
int seg_len = s.Length - k;
// Find value of first segment of seg_len
int res = 0;
for (int i = 0; i < seg_len; i++)
res = res * 10 + (s[i] - '0');
// Find value of remaining segments using
// sliding window
int seg_len_pow = (int)Math.Pow(10,
seg_len - 1);
int curr_val = res;
for (int i = 1;
i <= (s.Length- seg_len); i++) {
// To find value of current segment,
// first remove leading digit from
// previous value
curr_val = curr_val -
(s[i - 1] - '0') * seg_len_pow;
// Then add trailing digit
curr_val = curr_val * 10 +
(s[i + seg_len - 1] - '0');
res = Math.Max(res, curr_val);
}
return res;
}
// Driver code
public static void Main() {
String s = "8754";
int k = 2;
Console.WriteLine("Maximum number = "
+ findMaxSegment(s, k));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// JavaScript program to find the maximum segment
// value after putting k breaks.
// Function to Find Maximum Number
function findMaxSegment(s, k){
// Maximum segment length
let seg_len = s.length - k
// Find value of first segment of seg_len
let res = 0
for(let i=0;i<seg_len;i++)
res = res * 10 + (s.charCodeAt(i) - '0'.charCodeAt(0))
// Find value of remaining segments
// using sliding window
let seg_len_pow = Math.pow(10, seg_len - 1)
let curr_val = res
for(let i = 1;i< s.length - seg_len;i++){
// To find value of current segment,
// first remove leading digit from
// previous value
curr_val = curr_val - (s.charCodeAt(i - 1)-'0'.charCodeAt(0)) * seg_len_pow
// Then add trailing digit
curr_val = (curr_val * 10 +
(s.charCodeAt(i + seg_len - 1) - '0'.charCodeAt(0)))
res = Math.max(res, curr_val)
}
return res
}
// Driver Code
let s = "8754"
let k = 2
document.writea("Maximum number = ",findMaxSegment(s, k))
// This code is contributed by shinjanpatra
</script>
Producción:
Maximum number = 87
Complejidad temporal : O(n)
Espacio auxiliar : O(1)