Create two sub array of maximum equal height from an array.

Create two sub array of maximum equal height from an array.

Problem Statement:

There are N bricks (a1, a2, ...., aN). Each brick has length L1, L2, ...., LN). Make 2 highest parallel pillars (same length pillars) using the bricks provided.

Constraints:

There are N bricks. 5<=N<=50

Length of each brick. 1<=L<=1000

Sum of the bricks lengths <= 1000

Length of the bricks is not given in size order. There may be multiple bricks which may have the same length. Not all bricks have to be used to create the pillars.

Example:

1st Example-

N = 5

2, 3, 4, 1, 6

Possible Sets:

(2, 6) and (3, 4, 1)

Answer: 8

----------------------------------------------------------------------------------------------------------

To solve this problem, we need to partition the given array of bricks into two subsets such that the heights of the two subsets are equal and as high as possible. The height of a subset is simply the sum of its elements. Here’s a step-by-step approach to solve this problem:

Approach:

1. Calculate Total Sum: First, compute the total sum of all bricks. Let's denote this sum as $S$.

2. Determine Feasibility: For two subsets to have equal height, the total sum $S$ must be even. If $S$ is odd, it’s impossible to split it into two equal parts.

3. Dynamic Programming (DP) Approach: Use a DP approach to determine if a subset with a given sum is achievable. Specifically, we'll use a DP array where dp[i] indicates whether a subset with sum i can be formed using the bricks.

4. Subset Sum Calculation: Use the DP array to check for the maximum height that can be achieved, which is half of the total sum if it's feasible.

5. Result: The maximum height of the two subsets will be the largest possible subset sum that is achievable which is exactly half of the total sum.

Detailed Steps:

1. Initialization:

   • Calculate the total sum $S$ of the array.
   • Check if $S$ is even. If not, print 0 as it’s not possible to partition it into two equal parts.

2. Dynamic Programming Setup:

   • Create a boolean DP array dp of size $S/2 + 1$. Initialize dp[0] to True because a subset sum of 0 is always achievable (with an empty subset).

3. DP Array Update:

   • Iterate through each brick and update the DP array to reflect possible subset sums.

4. Result Extraction:

   • The largest index i in the DP array where dp[i] is True will give the maximum possible height of one subset. The other subset will automatically have the same height if $S$ is even.

Here's the Python code to achieve this:

python
def max_equal_height_pillars(bricks):
    total_sum = sum(bricks)
    
    # If total sum is odd, it's not possible to split into two equal parts
    if total_sum % 2 != 0:
        return 0
    
    target = total_sum // 2
    n = len(bricks)
    
    # DP array to check if subset with sum 'i' can be formed
    dp = [False] * (target + 1)
    dp[0] = True
    
    for brick in bricks:
        for i in range(target, brick - 1, -1):
            dp[i] = dp[i] or dp[i - brick]
    
    # Find the maximum sum which can be achieved which is less than or equal to 'target'
    for i in range(target, -1, -1):
        if dp[i]:
            return i

    return 0

# Example usage
bricks = [2, 3, 4, 1, 6]
print(max_equal_height_pillars(bricks))  # Output should be 8

Explanation:

• Initialization: Set up the DP array and initialize the first element to True.
• DP Array Update: Update possible sums using each brick.
• Result Extraction: Find the maximum possible subset sum that equals target.

This code efficiently finds the maximum height of two equal pillars using a dynamic programming approach to subset sum problems.

-----------------------------------------------------

Java Solution:

Here’s a Java program to solve the problem of partitioning bricks into two subsets of maximum equal height:

java
import java.util.Arrays;

public class MaxEqualHeightPillars {

    public static void main(String[] args) {
        int[] bricks = {2, 3, 4, 1, 6};
        System.out.println(maxEqualHeightPillars(bricks));
    }

    public static int maxEqualHeightPillars(int[] bricks) {
        int totalSum = Arrays.stream(bricks).sum();
        
        // If the total sum is odd, it's not possible to split into two equal parts
        if (totalSum % 2 != 0) {
            return 0;
        }
        
        int target = totalSum / 2;
        int n = bricks.length;
        
        // DP array to check if subset with sum 'i' can be formed
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        // Update DP array using each brick
        for (int brick : bricks) {
            for (int i = target; i >= brick; i--) {
                dp[i] = dp[i] || dp[i - brick];
            }
        }
        
        // Find the maximum sum which can be achieved which is less than or equal to 'target'
        for (int i = target; i >= 0; i--) {
            if (dp[i]) {
                return i;
            }
        }
        
        return 0;
    }
}

Explanation:

1. Calculate Total Sum: Sum all elements in the bricks array.
2. Check Feasibility: If totalSum is odd, return 0 because partitioning into two equal parts is not possible.
3. Dynamic Programming (DP) Setup:
   • Initialize a boolean array dp of size target + 1 to keep track of possible subset sums.
   • Set dp[0] to true because a subset sum of 0 is always possible.
4. Update DP Array:
   • For each brick, update the DP array in reverse order to avoid overwriting results of the current iteration.
5. Result Extraction:
   • Find the largest i where dp[i] is true, which represents the maximum possible height of one pillar.

How to Run:

1. Copy and paste the Java code into a file named MaxEqualHeightPillars.java.
2. Compile the Java file using javac MaxEqualHeightPillars.java.
3. Run the compiled class with java MaxEqualHeightPillars.

The program will print the maximum height of the two pillars that can be achieved using the provided bricks.