DP can help us to find max path, I couldn't find out any specific solution for complexity less than O(n!) but as an initial Idea, I think some kind of sorting rows or modified Floyd-Warshal algorithm may help us.please discuss If you have any Idea for challenge the problem.
On Sun, Aug 12, 2012 at 1:22 PM, MeHdi KaZemI <mehdi.kaze...@gmail.com>wrote: > Yes, and all the values are positive integers. > > For example > 1 2 > 3 4 > 5 6 > Maximum path in this matrix is 15, > > Another permutation of the same matrix > 5 6 > 1 2 > 3 4 > Maximum path in this matrix is 17, > We want the minimum value among these maximum paths. > > > On 8/12/12, MeHdi KaZemI <mehdi.kaze...@gmail.com> wrote: > > On 8/12/12, Hassan Monfared <hmonfa...@gmail.com> wrote: > >> do we sum all cell values when we step over them ? > >> > >> On Sun, Aug 12, 2012 at 12:42 PM, MeHdi KaZemI > >> <mehdi.kaze...@gmail.com>wrote: > >> > >>> Hi there, > >>> There is a integer Matrix with dimensions n*2, If you want to go from > >>> (1,1) to (n,2) and you are allowed just to go down or right, what's > >>> the maximum value you can get? Alright this is easy, but we want to > >>> consider all the permutations of rows of the matrix which is n!, find > >>> this maximum for each permutation, and finally we want the minimum > >>> amount among these maximum values. > >>> Do you have an Idea to solve this problem better than O(n!)? > >>> > >>> -- > >>> MeHdi KaZemI > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > >>> Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algogeeks@googlegroups.com. > >>> To unsubscribe from this group, send email to > >>> algogeeks+unsubscr...@googlegroups.com. > >>> For more options, visit this group at > >>> http://groups.google.com/group/algogeeks?hl=en. > >>> > >>> > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > >> > >> > > > > > > -- > > MeHdi KaZemI > > > > > -- > MeHdi KaZemI > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.