Given an array arr[] of N integers and an integer K, the task is to find the maximum subarray sum such that the subarray has at most K odd integers.
Example:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 1
Output: 15
Explanation: The subarray arr[3… 5] = {4, 5, 6} has only 1 odd integer i.e, 5 and the sum of all its elements is the maximum possible i.e, 15.Input: arr[] = {1, 1, 1, 1}, K = 0
Output: 0
Approach: The given problem can be solved using the sliding window technique similar to the approach discussed in the article here. Create a variable odd_cnt, which stores the number of odd integers in the current window. If the value of odd_cnt exceeds K at any point, decrease the window size from the start, otherwise include the element in the current window. Similarly, iterate for the complete array and maintain the maximum value of sum of all the windows in a variable max_sum.
Below is the implementation of the above approach:
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> |
15
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!