Originally Posted by
elad
For what they are worth here's my thoughts:
Problem 1:
Assuming the nondecreasing sequences need to be read left to right (if you flip the 7 and 3 at element 5 in the example you get a 4 element nondecreasing sequence going left to right) then you could find longest nondecreasing sequence(s) in each array and just flip the bracketing elements (start -1 and end + 1) to see if they extend the sequence.
Problem 2:
The max number of squares visited may not be the same sequence used to discover the max value obtained, as in the example. Are you supposed to have one, the other, or both? If you can only move down and to the right how can you back track? The maximum number of boxes visited without backtracking is 7, if I'm counting right. (00, 01, 02, 21, 22, 23, 33) or (00, 01, 02, 21, 22, 23, 33)
1:
Not sure I follow...
if you flip 7 and 3 at 5, you get:
Code:
7 5 8 2 3 2 1 0 5 3 1 3
3 6 1 6 7 0 0 4 3 2 4 3
which is two, not four.
2:
Supposed to have both...
I'm not really familiar with backtracking, but I know recursive functions can be very slow. Can't this be solved by dynamic programming, maybe? I don't really know how to implement backtracking here.
By the way, King Mir, you said go left at step 6. You can't go left, you can only go to the right or down...
