product of Maximum of all subarray-CodePudding

I have an Array with some distinct integer data in it and I need to get the max element from all the subarray possible and multiply it. Here is the example input : {4,7} Required Output: 196

Explanation: subarray possible

{4}=max{4}=4
{7}=max{7}=7
{4,7}=max{4,7}=7
answer=4*7*7=196

can someone help me with this? Thanks in advance.

CodePudding user response：

I don't know Java, but from a algorithmic point of view it could look like this:

max_list = empty_list
for i to len(A)
    for j to len(A) - i 
        subset [j, j i]
        find max of subset
        append max to max_list

result = 1
for i to len(A)
    result = result * A[i]

CodePudding user response：

Something like that?

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] arrays =  { {3, 3, 5, -1, -2}, 
                            {1, 2, 3}, 
                            {5, 4, 3, 2, 1} };

        System.out.println("Result: "   getProduct(arrays));
    }

    public static int getProduct(int[][] arrays) {
        int result = 1;
        for(int[] array : arrays){
            Arrays.sort(array);
            result *= array[array.length - 1];
        }
        return result;
    }
}

or in a more general way:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] arrays =  { { 3, 3, 5, -1, -2 }, 
                            { 1, 2, 3 }, 
                            { 5, 4, 3, 2, 1 } };

        System.out.println("Result: "   getProduct(arrays));

        System.out.println("Result: "   getProduct(new int[][]{ { 4 }, { 7 }, { 4, 7 } }));

        System.out.println("Result: "   getProduct(new int[]{ 9, 2, 5, -4, -8 }));

        System.out.println("Result: "   getProduct(new int[]{ 2 }));
    }

    public static int getProduct(int[][] arrays) {
        int result = 1;
        for(int[] array : arrays) result *= getProduct(array);
        return result;
    }

    public static int getProduct(int[] array) {
        Arrays.sort(array);
        return array[array.length - 1];
    }
}

CodePudding user response：

From what i know, this should do what you want:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[][] arrays = {
            {4},
            {7},
            {4, 7}
        };

        int result = Arrays.stream(arrays).mapToInt((x) -> Arrays.stream(x).max().getAsInt()).reduce(1, Math::multiplyExact);

        System.out.println(result);
    }
}

First, the largest value from each of the source arrays is selected.

Arrays.stream(arrays).mapToInt(x -> {});

To achieve this, we first iterate over each of these arrays in the lambda function of Arrays.stream and get the largest value in the array x by inserting

Arrays.stream(x).max().getAsInt()

In the last step, the largest numbers from the respective arrays are multiplied together, which is done by the reduce method, which always makes one out of two values until only one is left. The operation used to reduce is multiplyExact, the reason for this is that a method Integer::multiply unfortunately does not exist (or at least I don't know about it). The special thing about the method multiplyExact is that it throws an error as soon as an integer overflow occurs.

CodePudding user response：

If I understand the problem correctly, you need to construct all possible arrays of all possible lengths from a given set of elements (the original array), then calculate the product of maximums of each those possible arrays. Also, based on your example the order is unimportant (since there's no [4, 7] and [7, 4] in your example), so these are actually sets and not arrays.

Constructing all possible subsets of a set may be intensive but you may not need to actually do it, because all you need is the maximum element from each of the possible subsets.

You know that the smallest element (let's call it S0) will be the maximum of only one possible subset, [S0], so S0 goes into the final product once.

The second smallest element S1 will be the maximum value of only two possible subsets, [S1] and [S1, S0], so S1 goes into the final product twice...

The third smallest element S2 will be the max of how many sets?

[S2]
[S2, S0]
[S2, S1]
[S2, S0, S1]

Fourth-smallest S3?

[S3]
[S3, S2]
[S3, S1]
[S3, S0]
[S3, S2, S1]
[S3, S2, S0]
[S3, S1, S0]
[S3, S2, S1, S0]

So each N-th smallest will be 2^N times included in the product, since 2^N is the number of possible sets of N elements of length 0..N when the order doesn't matter.