# Brute Force Longest Non-Decreasing Sub-Sequence

## Table of Contents

## The Problem

The problem at hand is that we're given a sequence and we want to find the longest combination we can find in it that is non-decreasing (each element after the first is greater than or equal to the previous element).

## Brute Force

This will be a brute-force solution using nested for-loops. This will use the itertools.combinations function to generate the candidate solutions.

```
from itertools import combinations
```

```
def brute_force(sequence: iter) -> tuple:
"""Finds the longest non-decreasing sub-sequence
Args:
sequence: the source collection of items
Returns:
the longest non-decreasing sub-sequence in the sequence, number of for-loops
"""
count = 0
for length in range(len(sequence), 0, -1):
count += 1
for sub_sequence in combinations(sequence, length):
count += 1
if list(sub_sequence) == sorted(sub_sequence):
return sub_sequence, count
return
```

Here's what it's doing.

- The outer loop counts down from the length of the sequence to zero.
- The inner loop generates combinations of the current length in the outer loop
- If the
`sub_sequence`

is in sorted (non-decreasing) order then it is as long or longer than any other non-decreasing sub-sequence so choose it as the longest sub-sequence.

### Example One

```
source = (3, 1, 0, 2, 4)
expected = (1, 2, 4)
actual, count = brute_force(source)
print(actual)
print(count)
assert actual == expected
```

(1, 2, 4) 18

## End

- From Python Algorithms