# Brute Force Longest Non-Decreasing Sub-Sequence

## 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.

1. The outer loop counts down from the length of the sequence to zero.
2. The inner loop generates combinations of the current length in the outer loop
3. 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
```