New answers tagged optimization
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:
$$
\begin{equation}
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