Mr. Navin ! the main question is not about finding max path for one permutation among the n! permutations! please read the question again and join us for solving the main problem
On Sun, Aug 12, 2012 at 4:19 PM, Navin Kumar <algorithm.i...@gmail.com>wrote: > We can solve using Dynamic programming.. > Take n*2 matrix for storing sum. Let A be original matrix and matrix M > hold sum. Let M[i, j] contains max sum upto i th row and j th column. > > recursion will be as follows: > > M[i, j] = max(M[i - 1, j], M[i, j-1]) + A[i, j] > > By above formula fill whole M matrix and return the M[n-1, 1] value. > > P.S. I have not written boundary condition. For this if M[i - 1, j] goes > beyond matrix boundary then take M[i, j-1] value and vice versa. Initialize > M[0, 0] = A[0, 0] > > > On Sun, Aug 12, 2012 at 3:16 PM, Hassan Monfared <hmonfa...@gmail.com>wrote: > >> 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. >> > > -- > 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.
