|
Given two integers X and Y. X and Y represent the frequency of elements 1 and -2 you have. You have to arrange all elements such that the maximum sum over all subarrays is minimized, and then find the maximum subarray sum of such rearrangement.
Examples:
Input: X = 1, Y = 1
Output: 1
Explanation: X = 1 and Y = 1 means we have one 1 and one -2. There can be only two possible arrangements with these elements as {1, -2} or {-2, 1}. In both of the cases the maximum subarray sum will be 1.
Input: X = 5, Y = 1
Output: 3
Explanation: The optimal arrangement of elements will be {1, 1, -2, 1, 1, 1}. Then, the maximum subarray sum will be 3.
Approach: To solve the problem, follow the below idea:
- In case the number of 1’s are too great, the -2s won’t affect the subarray sum too much. Hence, we also calculate the sum of the whole array, which is (X – 2*Y) (Since the whole array is also its own subarray).
- If there are Y number of -2s then there will be (Y+1) groups of 1s in arrangement. For example, X = 5 and Y = 2, then the arrangement will be as follows: {}, -2, {}, -2, {}. Where “{}” shows the collective group of ones (equal to (Y+1) = 3). We need to distribute X number of 1s in (Y+1) spaces equally. So that the distribution will be as Ceil (X/ (Y+1)).
- Then, the maximum subarray sum will be max of both of these as max((X – 2*Y), Ceil (X/ (Y+1))).
- The problem is observation based. The main idea is, for any subarray to have its sum minimized, we need to distribute the 1s among the -2s such that the count of 1s in between -2s are smallest. This can only be done by optimally dividing the number of 1’s between the 2’s.
Illustration:
Let us understand it with some examples and find some observations:
- Example 1: X = 5, Y = 2
- We have five 1s and two -2s.
- We need to distribute 1s in between -2s, then the optimal arrangement will be as follows: {1, 1, -2, 1, -2, 1, 1}. The maximum subarray sum will be 2 in this case. Max((X – 2*Y), Ciel (X/ (Y+1))) = 2.
- Example 2: X = 5, Y = 1
- We have five 1s and one -2s.
- The optimal arrangement will be as follows: {1, 1, -2, 1, 1, 1}. The maximum subarray sum will be 3 in this case. Ceil(5/(1+1)) = 3. Max((X – 2*Y), Ciel (X/ (Y+1))) = 3.
- Example 3: X = 1, Y = 3
- We have one 1 and three -2s.
- The optimal arrangement will be as follows: {-2, -2, -2, 1}. The maximum subarray sum will be 1. Max((X – 2*Y), Ciel (X/ (Y+1))) = 1.
Step-by-step algorithm:
- Declare two variables let say A and B.
- Initialize A with Ciel (X/ (Y+1)).
- Initialize B with sum of all elements as (X – 2*Y).
- Output Max (A, B).
Below is the implementation of the algorithm:
C++
#include <iostream>
#include <cmath>
void FindMaxSum(double X, double Y)
{
double A = std::ceil(X / (Y + 1.0));
double B = (X - 2 * Y);
std::cout << std::max(A, B) << std::endl;
}
int main()
{
double X = 5, Y = 2;
FindMaxSum(X, Y);
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void main(String[] args)
{
double X = 5, Y = 2;
FindMaxSum(X, Y);
}
public static void FindMaxSum(Double X, Double Y)
{
double A = Math.ceil(X / (Y + 1.0));
double B = (X - 2 * Y);
System.out.println(Math.max(A, B));
}
}
|
Python3
import math
def find_max_sum(X, Y):
A = math.ceil(X / (Y + 1.0))
B = X - 2 * Y
return max(A, B)
X = 5
Y = 2
max_sum = find_max_sum(X, Y)
print(max_sum)
|
C#
using System;
public class GFG
{
public static void Main(string[] args)
{
double X = 5, Y = 2;
FindMaxSum(X, Y);
}
public static void FindMaxSum(double X, double Y)
{
double A = Math.Ceiling(X / (Y + 1.0));
double B = (X - 2 * Y);
Console.WriteLine(Math.Max(A, B));
}
}
|
Javascript
function findMaxSum(X, Y) {
let A = Math.ceil(X / (Y + 1));
let B = X - 2 * Y;
console.log(Math.max(A, B));
}
function main() {
let X = 5, Y = 2;
findMaxSum(X, Y);
}
main();
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
-768.webp){kind=small}