Jak wyznaczyć liczbę podciągów malejących w tablicy

hejka, potrzebuje pomocy w napisaniu programu który będzie wyznaczał podciągi malejące z ciągu.
Przykład:
Wejście: A[] = [ 5, 4, 2, 2, 1]
Wyjście: Liczba wszystkich podciągów malejących to 4
[5, 4], [5, 4, 2], [4, 2], [2,1]

Jestem kompletnie zielony w programowaniu i nie mam pojęcia jak się zabrać za ten program nawet ;/

W jaki sposób wyszukałbyś takie podciągi na kartce, ręcznie?

@Patryk27: na kartce nie byłoby problemu, ale muszę napisać program który będzie je wyznaczał sam

Coś takiego, ale pisane z palca, trzeba potestować:

function solution(xs):
  limit = length(xs)
  if limit < 2: 
    return 0
  cnt = 0
  for ind = 1 to limit - 1:
    j = ind
    while j + 1 < limit:
      if xs[j] > xs[j + 1]:
        cnt += 1
      else:
        break
      j += 1
  return cnt

print(solution([ 5, 4, 2, 2, 1]))  # -> 4

Nie chodzi o to czy to jest problem na kartce tylko o podejście do rozwiązania tego problemu na kartce. Stworzenie sobie takiego opisowego algorytmu, nawet najbardziej prymitywnego na początek.

1. biorę pierwszy element jako startowy
2. sprawdzam kolejny element w liście, jeśli
3. a) jest mniejszy od poprzedniego to zapisuje to jako podciąg (od punktu startowego) i wracam do pkt 2
4. b) jeśli nie jest mniejszy to jako punkt startowy biorę kolejny element w liście

Chodzi o taki opis (pisałem na oko, więc może być bzdurny, ale nie to jest tutaj najważniejsze). Jeżeli potrafisz zrobić taki opis, to łatwo będziesz to w stanie przenieść na pseudokod a z pseudokodu to już prosta droga do napisania tego w C++.

No i zakładamy trochę, że chcesz pomoc a nie gotowca.

**Podciąg **– ciąg powstały poprzez wybranie pewnej liczby wyrazów ciągu wyjściowego.

Stąd zadanie jest trochę trudniejsze ( jeżeli rzeczywiście chodzi tutaj o podciągi ), gdyż dla następującego ciągu

[ 5, 4, 2, 2, 1 ]

jego podciągi malejące to:

[5, 4], [5, 4, 2], [4, 2], [2,1], [5, 2], [5, 1], [5, 2, 1], [4, 2, 1], [5, 4, 2, 1]

na kartce nie byłoby problemu

Ok, zatem: w jaki sposób wyszukałbyś takie podciągi na kartce, ręcznie? :-)

Wyjście: Liczba wszystkich podciągów malejących

Wystarczy wyznaczyć długość kolejnych najdłuższych ciągów malejących, a potem zsumować odpowiedni wzór zależny od długości ciągu, żadna filozofia.