How to find the maximum possible sum of numbers in arrays drawn from a unique array index

Question

I need to find maximum possible sum of numbers in arrays but number must be drawn from a unique array index...just like that:

double maxSum = 0;

double a = {1.0 , 2.0, 3.0};
double b = {4.0 , 5.0, 6.0};
double c = {7.0 , 8.0, 9.0};

sum = a[0] + b[1] + c[2];

// or sum = a[0] + b[2] + c[1]
// or sum = a[1] + b[0] + c[2]
// etc. - how to do that for i arrays and for j numbers in array?

if(sum >=maxSum){
maxSum = sum;
}

this is what I did - but don't have any clue what to do next...

    public ArrayList<Double[]> tempArrayCreator() {
    ArrayList<Double[]> lists = new ArrayList<Double[]>();

    Double[] list1 = { 6.0, 7.0, 6.0 };
    Double[] list2 = { 4.5, 6.0, 6.75 };
    Double[] list3 = { 6.0, 5.0, 9.0 };

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);

    return lists;
}

public double maxPossibleSum(ArrayList<Double[]> lists) {

    double result = 0.0;

    for (int i = 0; i < lists.size(); i++) {
        for (int j = 0; j < lists.get(i).length; j++) {

        // ???

        }
    }

    return result;

}

edit. example:

list1 = { 1, 5, 2};
list2 = { 9, 3, 7};
list3 = { 8, 4, 9};

possible solutions:
list1[0] + list2[1] + list3[2] = 13
list1[0] + list2[2] + list3[1] = 12
list1[1] + list2[0] + list3[2] = 23 <-- here it is!
list1[1] + list2[2] + list3[0] = 20
list1[2] + list2[0] + list3[1] = 15
list1[2] + list2[1] + list3[0] = 13

Why not add the value from the array into your result variable? — Patrick J Abare II, Sep 03 '14 at 12:14
Am I right in thinking that: a) All of the source arrays will have the same number of elements and b) Each unique index where 0 <= index < arrayLength must be used once and only once? — GHC, Sep 03 '14 at 12:19
I'm a little confused about what you're trying to do. It sounds like you want to sum the largest number from each list? Can you clarify your expected result. — Moob, Sep 03 '14 at 12:22
I think it is specified in comments in code "how to do that for i arrays and for j numbers in array?" — Vihar, Sep 03 '14 at 12:23
@Moob I want to get maximum sum from numbers drawn from unique array index - in my example I should get 21.0 - list1[0]+list2[1]+list3[2] — Aleizdein, Sep 03 '14 at 12:31
i think i can explain, you need to find the numbers (a number from each array) that if you sum together will result the maximum possible sum, the result could be array1[4] + array2[11] + arrayN[X] based on where N is the count of arrays — Yazan, Sep 03 '14 at 12:31
@GHC yes - every array will have the same number of elements and each index I can use only once — Aleizdein, Sep 03 '14 at 12:36
@Moob in fact, the correct result is 22.75, check my answer below :) — Yazan, Sep 03 '14 at 12:41

score 3 · Accepted Answer · edited May 23 '17 at 12:21

First, you want to get the list of all the Permutations of your indexes.

{[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 1, 0], [2, 0, 1]}

For example, this answer gives a way to do it:

public static List<List<Integer>> getAllPermutations(int arraySize) {
    List<Integer> elements = new ArrayList<Integer>();
    for (int i = 0; i < arraySize; i++) {
        elements.add(i);
    }
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    getAllPermutations(result, elements, 0);
    return result;
}

private static void getAllPermutations(List<List<Integer>> result, List<Integer> elements, int k) {
    for (int i = k; i < elements.size(); i++) {
        java.util.Collections.swap(elements, i, k);
        getAllPermutations(result, elements, k + 1);
        java.util.Collections.swap(elements, k, i);
    }
    if (k == elements.size() - 1) {
        result.add(new ArrayList<Integer>(elements));
    }
}

Then you iterate through all your permutations:

public double maxPossibleSum(ArrayList<Double[]> lists) {
    List<List<Integer>> allPermutations = getAllPermutations(3);
    double maxSum = Double.NEGATIVE_INFINITY;
    for (List<Integer> permutation : allPermutations) {
        double sum = 0;
        for (int i = 0; i < permutation.size(); i++) {
            Integer index = permutation.get(i);
            sum += lists.get(i)[index];
        }
        if (sum > maxSum) {
            maxSum = sum;
        }
    }
    return maxSum;
}

Please explicit your sources. Otherwise proposed code is fine — olivieradam666, Sep 03 '14 at 12:55

score 0 · Answer 2 · answered Sep 03 '14 at 12:16

0

    for (int i = 0; i < lists.size(); i++) {
        Double[] tmp = list.get(i);
        for (int j = 0; j < tmp.length; j++) {
            result += tmp[j];     
        }           

    }

answered Sep 03 '14 at 12:16

Patrick J Abare II

1,129
1
10
31

score 0 · Answer 3 · answered Sep 03 '14 at 12:16

0

inside your for loop just add

result+=lists.get(i)[j];

answered Sep 03 '14 at 12:16

Vihar

3,626
2
24
47

thank you for this - but in that way I get sum of all numbers in all arrays - and what I want is to get maximum possible sum of only one number from each array (and in unique array index as well) – Aleizdein Sep 03 '14 at 12:33
can you put an example in your question? its pretty confusing to understand what you are really asking for – Vihar Sep 03 '14 at 12:35

How to find the maximum possible sum of numbers in arrays drawn from a unique array index

3 Answers3

Linked