1

I have a problem with this exercise - I have to find the biggest descending sequence in a list of numbers, but I can "skip" numbers which would screw up my sequence. Output is the length of the biggest sequence.

Example:
Input:
22.155 23.252 22.586 22.450 23.372 22.228 22.087 23.091 22.190 22.140 22.057 22.123 22.359 22.190 22.140 22.523 22.384 22.488 23.201 23.050
Output:
7

The biggest sequence in the example is:
22.155 23.252 22.586 22.450 23.372 22.228 22.087 23.091 22.190 22.140 22.057 22.123 22.359 22.190 22.140 22.523 22.384 22.488 23.201 23.050

I had some ideas, but I couldn't implement them/it turned out they are wrong.

  • find all descending sequences and return the biggest one (I have no idea how to do it and I think that this is not the smartest way)
  • the second idea is quite complicated and it's hard for me to explain it, because my English is bad
  1. Find the mainNumber, which has the most numbers lower than the mainNumber (those numbers have to be on the right side of the mainNumber - for example:
    22.155 23.252 22.586 22.450 23.372 22.228 22.087 23.091 22.190 22.140 22.057 22.123 22.359 22.190 22.140 22.523 22.384 22.488 23.201 23.050
    when the mainNumber is 22.450 you only analyze: 23.372, 22.228, 22.087, etc., not the first three
  2. Now find the new mainNumber, but your sequence starts from the actual mainNumber
  3. Repeat until there are no more number lower than mainNumber

Here is my code (I am aware that probably you will say it is terrible) I also can't find out what condition should I put in my while loop, so just for now I put 1. And I know that the printed indexes are wrong.

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]

best = 0
count = 0
index = 0

while 1:
    for i in range(index+1, len(times)):
        for j in range(i+1, len(times)):
            if times[j] < times[i]:
                count += 1
        if count > best:
            best = count
            index = i
        count = 0
    best = 0

    print(index)

I would be very grateful for any help. I have no clue what can I do more. Sorry for my bad english.

kstajer
  • 55
  • 4
  • `23.091, 22.19, 22.14, 22.057` is the largest descending sequence. – Booboo Jan 10 '21 at 14:22
  • 1
    @Booboo Subsequences need not be contiguous. – kaya3 Jan 10 '21 at 14:30
  • @kaya3 Is "but I can "skip" numbers which would screw up my sequence" a precise specification? And what is a `mainNumber`? Do you mean skip the number that break the descending sequence? If so, then `23.252 22.586 22.450` as indicated by the OP is *not* a solution. – Booboo Jan 10 '21 at 14:59
  • @Booboo The example in the question shows a solution which is not contiguous. There are 7 numbers bolded, not 3. – kaya3 Jan 10 '21 at 17:30
  • @kaya3 I got it, finally. – Booboo Jan 10 '21 at 18:02

1 Answers1

1

For biggest descending order you can use two loops

Contiguous

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = 0
start_index = 0
end_index = 0

for i in range(times_len):
  for j in range(i + 1, times_len):
    # break previous number is bigger than current number
    if times[j] > times[j -1]:
      break
  distance = j - i
  if distance > best:
    best = distance
    start_index = i
    end_index = j

print(times[start_index:end_index])

Output

[23.091, 22.19, 22.14, 22.057]

A better approach

You can optimize your algorithm by skipping visited numbers with below code.

i = 0
while i < times_len:
  for j in range(i + 1, times_len):
    # break previous number is bigger than current number
    if times[j] > times[j -1]:
      break
  distance = j - i
  if distance > best:
    best = distance
    start_index = i
    end_index = j
    i = j         # skip numbers
  else:
    i += 1

print(times[start_index:end_index])

Non-Contiguous 1

Simpler non-contiguous

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = 0
best_values = []

for i in range(times_len):
  values = [times[i]]
  for j in range(i + 1, times_len):
    if values[-1] > times[j]:
      values.append(times[j])
      
  if len(values) > best:
    best = len(values)
    best_values = values

print(best_values)

Output

[23.252, 22.586, 22.45, 22.228, 22.087, 22.057]

Non-Contiguous 2

Complex non-contiguous way. I have created an algorithm maybe there are faster ways. It works with recursively and compares with best values.

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = []

def search(values, j):
  best = []
  while j < times_len:
    if values[-1] >= times[j]:
      copy_values = values.copy()
      copy_values.append(times[j])
      result = search(copy_values, j + 1)
      if len(result) > len(best):
        best = result
    else:
      # remove lower values and start a new list
      for k in range(len(values) - 2, 0, -1):
        if values[k] >= times[j]:
          sub_values = values[:k]
          sub_values.append(times[j])
          result = search(sub_values, j + 1)
          if len(result) > len(best):
            best = result
          break
    j += 1
    
  if len(values) > len(best):
    best = values
  return best
    

for i in range(times_len):
  values = search([times[i]], i + 1)
  if len(values) > len(best):
    best = values

print(best)

Output

[23.252, 22.586, 22.45, 22.228, 22.19, 22.14, 22.057]
Ismail Durmaz
  • 2,521
  • 1
  • 6
  • 19