Dado un arreglo arr[] de N enteros y un entero K , la tarea es encontrar la suma máxima del subarreglo tal que el subarreglo tenga como máximo K enteros impares.
Ejemplo:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 1
Salida: 15
Explicación: El subarreglo arr[3… 5] = {4, 5, 6} tiene solo 1 entero impar, es decir , 5 y la suma de todos sus elementos es el máximo posible, es decir, 15.Entrada: arr[] = {1, 1, 1, 1}, K = 0
Salida: 0
Enfoque: El problema dado se puede resolver usando la técnica de ventana deslizante similar al enfoque discutido en el artículo aquí . Cree una variable odd_cnt , que almacena el número de enteros impares en la ventana actual. Si el valor de odd_cnt supera a K en algún punto, reduzca el tamaño de la ventana desde el principio; de lo contrario, incluya el elemento en la ventana actual. De manera similar, itere por la array completa y mantenga el valor máximo de la suma de todas las ventanas en una variable max_sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// To find subarray with maximum sum
// having at most K odd integers
int findMaxSubarraySum(int arr[], int n, int K)
{
// To store current sum and
// max sum of subarrays
int curr_sum = arr[0],
max_sum = 0, start = 0;
// Stores the count of odd integers in
// the current window
int odd_cnt = arr[0] % 2;
// Loop to iterate through the given array
for (int i = 1; i < n; i++) {
// If odd_cnt becomes greater than
// K start removing starting elements
while (start < i
&& odd_cnt + arr[i] % 2 > K) {
curr_sum -= arr[start];
odd_cnt -= arr[start] % 2;
start++;
}
// Update max_sum
max_sum = max(max_sum, curr_sum);
// If cur_sum becomes negative then
// start new subarray
if (curr_sum < 0) {
curr_sum = 0;
}
// Add elements to curr_sum
curr_sum += arr[i];
odd_cnt += arr[i] % 2;
}
// Adding an extra check for last subarray
if (odd_cnt <= K)
max_sum = max(max_sum, curr_sum);
// Return Answer
return max_sum;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 1;
cout << findMaxSubarraySum(arr, N, K);
return 0;
}
Java
// Java program of the above approach
class GFG
{
// To find subarray with maximum sum
// having at most K odd integers
public static int findMaxSubarraySum(int arr[], int n, int K)
{
// To store current sum and
// max sum of subarrays
int curr_sum = arr[0], max_sum = 0, start = 0;
// Stores the count of odd integers in
// the current window
int odd_cnt = arr[0] % 2;
// Loop to iterate through the given array
for (int i = 1; i < n; i++) {
// If odd_cnt becomes greater than
// K start removing starting elements
while (start < i && odd_cnt + arr[i] % 2 > K) {
curr_sum -= arr[start];
odd_cnt -= arr[start] % 2;
start++;
}
// Update max_sum
max_sum = Math.max(max_sum, curr_sum);
// If cur_sum becomes negative then
// start new subarray
if (curr_sum < 0) {
curr_sum = 0;
}
// Add elements to curr_sum
curr_sum += arr[i];
odd_cnt += arr[i] % 2;
}
// Adding an extra check for last subarray
if (odd_cnt <= K)
max_sum = Math.max(max_sum, curr_sum);
// Return Answer
return max_sum;
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = arr.length;
int K = 1;
System.out.println(findMaxSubarraySum(arr, N, K));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python program of the above approach # To find subarray with maximum sum # having at most K odd integers def findMaxSubarraySum(arr, n, K): # To store current sum and # max sum of subarrays curr_sum = arr[0] max_sum = 0 start = 0 # Stores the count of odd integers in # the current window odd_cnt = arr[0] % 2 # Loop to iterate through the given array for i in range(1, n): # If odd_cnt becomes greater than # K start removing starting elements while (start < i and odd_cnt + arr[i] % 2 > K): curr_sum -= arr[start] odd_cnt -= arr[start] % 2 start += 1 # Update max_sum max_sum = max(max_sum, curr_sum) # If cur_sum becomes negative then # start new subarray if (curr_sum < 0): curr_sum = 0 # Add elements to curr_sum curr_sum += arr[i] odd_cnt += arr[i] % 2 # Adding an extra check for last subarray if (odd_cnt <= K): max_sum = max(max_sum, curr_sum) # Return Answer return max_sum # Driver Code if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] N = len(arr) K = 1 print(findMaxSubarraySum(arr, N, K)) # This code is contributed by rakeshsahni
C#
// C# program of the above approach
using System;
class GFG
{
// To find subarray with maximum sum
// having at most K odd integers
public static int findMaxSubarraySum(int[] arr, int n, int K)
{
// To store current sum and
// max sum of subarrays
int curr_sum = arr[0], max_sum = 0, start = 0;
// Stores the count of odd integers in
// the current window
int odd_cnt = arr[0] % 2;
// Loop to iterate through the given array
for (int i = 1; i < n; i++)
{
// If odd_cnt becomes greater than
// K start removing starting elements
while (start < i && odd_cnt + arr[i] % 2 > K)
{
curr_sum -= arr[start];
odd_cnt -= arr[start] % 2;
start++;
}
// Update max_sum
max_sum = Math.Max(max_sum, curr_sum);
// If cur_sum becomes negative then
// start new subarray
if (curr_sum < 0)
{
curr_sum = 0;
}
// Add elements to curr_sum
curr_sum += arr[i];
odd_cnt += arr[i] % 2;
}
// Adding an extra check for last subarray
if (odd_cnt <= K)
max_sum = Math.Max(max_sum, curr_sum);
// Return Answer
return max_sum;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int N = arr.Length;
int K = 1;
Console.Write(findMaxSubarraySum(arr, N, K));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// Javascript program of the above approach
// To find subarray with maximum sum
// having at most K odd integers
function findMaxSubarraySum(arr, n, K)
{
// To store current sum and
// max sum of subarrays
let curr_sum = arr[0],
max_sum = 0, start = 0;
// Stores the count of odd integers in
// the current window
let odd_cnt = arr[0] % 2;
// Loop to iterate through the given array
for (let i = 1; i < n; i++) {
// If odd_cnt becomes greater than
// K start removing starting elements
while (start < i
&& odd_cnt + arr[i] % 2 > K) {
curr_sum -= arr[start];
odd_cnt -= arr[start] % 2;
start++;
}
// Update max_sum
max_sum = Math.max(max_sum, curr_sum);
// If cur_sum becomes negative then
// start new subarray
if (curr_sum < 0) {
curr_sum = 0;
}
// Add elements to curr_sum
curr_sum += arr[i];
odd_cnt += arr[i] % 2;
}
// Adding an extra check for last subarray
if (odd_cnt <= K)
max_sum = Math.max(max_sum, curr_sum);
// Return Answer
return max_sum;
}
// Driver Code
let arr = [1, 2, 3, 4, 5, 6];
let N = arr.length;
let K = 1;
document.write(findMaxSubarraySum(arr, N, K));
// This code is contributed by saurabh_jaiswal.
</script>
Producción
15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prabaljainn y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA