# Maximum non adjacent subsequence

Given an arrays of \(A\) size \(N\), find a sequence of non adjacent value with the larger sum, the sequence should be something like \(A_i, A_{i+k}, A_{i+k'}, \cdots, A_{i+k^n}, \forall k > 1\)

It’s easy to solve this problem with dynamic programming

Using a similar intuition it’s possible to come up with a linear solution

By analyzing all possible cases we see that

- if
`incl > excl + v[i]`

we don’t care for the current value, hence we can decide both to consider the next element or to skip it. So`incl`

is going to be equal to`excl`

- if
`incl < excl + v[i]`

then`incl`

has the current value, while`excl`

is set to the previous value of`incl`

Basically at every iteration `incl`

and `excl`

are swapped (except for the case when using a value doesn’t led to a better solution)

## Enjoy Reading This Article?

Here are some more articles you might like to read next: