Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.
Finding the maximum sum from a 2D array with a catch
I'm trying to find an algorithm in Java that determines the maximum result from adding together a combination of row column values in a 2D array. The limitation is that once a particular (row,column) value is chosen, no other entries in that row or column can be used in the calculation.
e.g. The 2D array below would return the maximum value of
c0 c1 c2
r0 1 4 7
r1 3 6 8
All possible combinations are:
1+6 = 7
1+8 = 9
4+3 = 7
4+8 = 12
7+3 = 10
7+6 = 13
So the maximum result is 12.
I have an algorithm at the moment that can find all these combinations and select the best one but it is very inefficient and uses up too much memory. It keeps track of all the possible combinations.
If anyone can help it would be greatly appreciated.