Largest value is of course A(n) + B(n). Second largest value is either A(n) + B(n-1) or A(n-1) + B(n).
Select the largest among both and continue down that array. Maintain 2 pairs: Pair 1: Hold first value constant, go down the second array. Pair 2: Hold 2nd value const. and go down the first array. Whenever one element of a pair cannot find a partner, that implies that all pairs containing that element have been considered. Discard that partner-less element and continue down the array. Take special care that duplicate elements are not output. See the output below so that things are clearer. (The duplicates case arises when the pair chosen in both cases is the same). eg. 1 7 9 2 3 4 Pair 1: (9,4) Pair 2: (9,4) -> Output (9,4) = 13 Pair 1: (9, 3) Pair 2: (7,4) -> Output (9,3) = 12 Pair 1: (9, 2) Pair 2: (7,4) -> Output (7,4) or (9,2) -- assume (9,2) was output = 11 Pair 1: (7,4) Pair 2: (7,4) -> Ouput (7,4) = 11 Pair 1: (7,3) Pair 2: (1, 4) -> Output (7, 3) = 10 Pair 1: (7,2) Pair 2: (1,4) -> Output (7,2) = 9 Pair 1: (1,4) Pair 2: (1,4) -> Output (1,4) = 5 Pair 1: (1,3) Pair 2: (1,3) -> Output (1,3) = 4 Pair 1: (1,2) Pair 2: (1,2) -> Output (1,2) = 3 Pair 1: (empty) Pair 2: (empty) -> End O(N) algorithm. Descending order printing of pairs. @Sunny: Your time complexity is O(N^2) as creating that array will take O(N^2) time. @Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but (9,3) will not. -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/uJEiQKMYJnMJ. 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.
