# Tag Info

0

If the coordinates of $a$ change, you just need to update one row and one column corresponding to $a$, not the whole matrix. This is done in linear time rather than quadratic time in your algorithm.

0

If the path is stored as a doubly-linked list, you can do it in $O(1)$ time in a straightforward way: you have to change around 4 edges, and each change can be done in $O(1)$ time. With an array it takes $O(n)$ time but is also straightforward to implement.

1

By using dynamic programming, we can solve this! Negative values also work. Let's start off with the subproblems. We would like to know $OPT(i,j)$, the maximum value of a consecutive subsequence from index $i$ to index $j$. Then the recurrence equation looks like this:  OPT(i,j)=\begin{cases} v_i & \text{if $i=j$,}\\ \max \{ ...

0

There is a straightforward dynamic programming algorithm. You only need to know, for each $i,j$, the length of the shortest path to $(x_i,y_j)$ that covers the first $i$ points, and the length of the shortest path to $(x_j,y_i)$ that covers the first $i$ points. I'll let you discover why that suffices. You should be able to take it from here. See our ...

Top 50 recent answers are included