Dots
Information
![{\displaystyle {\begin{aligned}x&={\begin{bmatrix}1\\0\end{bmatrix}}\\v&={\begin{bmatrix}v_{1},v_{2}\end{bmatrix}}\\R&={\begin{bmatrix}\cos(\theta )&-\sin(\theta )\\\sin(\theta )&\cos(\theta )\end{bmatrix}}\\Rx&={\begin{bmatrix}\cos(\theta )\\\sin(\theta )\end{bmatrix}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e6515660ed81a9842c81a24bceacbf1d77dec26)
...
![{\displaystyle {\begin{aligned}dot(Rx,v)-|v|&=0\\v_{1}\cos(\theta )+v_{2}\sin(\theta )-{\sqrt {v_{1}^{2}+v_{2}^{2}}}&=0\\v_{1}\cos(\theta )+v_{2}\sin(\theta )&={\sqrt {v_{1}^{2}+v_{2}^{2}}}\\(v_{1}\cos(\theta )+v_{2}\sin(\theta ))^{2}=v_{1}^{2}+v_{2}^{2}\\v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )&=v_{1}^{2}+v_{2}^{2}\\v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )-v_{1}^{2}-v_{2}^{2}&=0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e3a5cb102fb24f4324da779692fdafb8fe51c44)
...
![{\displaystyle {\begin{aligned}F(v_{1},v_{2},\theta )&=v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )-v_{1}^{2}-v_{2}^{2}\\DF(v_{1},v_{2},\theta )&={\begin{bmatrix}2v_{1}\cos ^{2}(\theta )+v_{2}\cos(\theta )\sin(\theta )-2v_{1}\\2v_{2}\sin ^{2}(\theta )+v_{1}\cos(\theta )\sin(\theta )-2v_{2}\\(2v_{2}^{2}-2v_{1}^{2})\cos(\theta )\sin(\theta )+v_{1}v_{2}(\cos ^{2}(\theta )-\sin ^{2}(\theta ))\\\end{bmatrix}}^{T}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f498ea1e623e27584773a937cb21ebf48a8c3cb6)
Not solvable when:
![{\displaystyle {\begin{aligned}(2v_{2}^{2}-2v_{1}^{2})\cos(\theta )\sin(\theta )+v_{1}v_{2}(\cos ^{2}(\theta )-\sin ^{2}(\theta ))=0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9abb93d620c32c25202921e63587439f7a65dc4d)
Monotonically Increasing
Information
Given a sequence of n numbers:
Want to find the longest monotonically increasing subsequence.
Define the function
as the length of the longest monotonically increasing subsequence in the first n elements.
Algorithm
Algorithm MonotonicIncrease(S, n)
Input
S - A sequence of numbers
.
n - The length of the sequence S.
Output
A monotonically increasing subsequence of S of maximal length.
Begin
L <- An array of n integers with L[k] is the length of the longest monotonic
subsequence in
.
D <- An array of n integers where D[k] holds the index of the previous
number in the longest monotonic sequence in
ending with
. Initially filled with 0's.
// Build the dynamic program
L[1] <- 1
for
longest <- 0
for
if
if
longest <- j
D[i] <- longest
L[i] <- L[longest] + 1
// Find the endpoint of the longest sequence
f <- 1
for
if
f <- i
// Print the solution
PrintMonotonicIncrease(S, D, f)
End
Algorithm PrintMonotonicIncrease(S, D, f)
Input
S - A sequence of numbers
.
D - An array of n integers where D[k] holds the index of the previous
number in the longest monotonic sequence in
ending with
.
f - The index of the final integer in the solution.
Output
The optimal sequence.
Begin
if
PrintMonotonicIncrease(S, D, D[f])
print S[f]
End
Test Work
Try this out...
o---o---o---o---o---o---o---o
| 1 | 4 | 2 | 7 | 8 | 4 | 5 |
o---o---o---o---o---o---o---o
| 1 | 2 | 2 | 3 | 4 | 4 | 4 |
o---o---o---o---o---o---o---o
And this...
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 3 | 3 | 7 | 2 | 6 | 4 | 5 | 6 | 1 | 8 | 3 | 2 | 6 |
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 |1 2|2 3|3 4|1 2|3 4|3 4|7 5|8 6|1 2|9 7|3 4|5 3|9 7|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o