Comment trouver la plus longue sous-suite croissante sans tri ?

Je veux trouver la plus longue sous-séquence croissante sans la trier, puis additionner les nombres de la période, par exemple comme:

17, 18, 19, 5, 6, 23, 24, 25, 24, 25

• 17, 18, 19est une sous-suite croissante.


• 5, 6, 23, 24, 25est une autre sous-suite croissante.

mais puisque 5, 6, 23, 24, 25sont 5des éléments et 17, 18, 19sont 3qui est inférieur à 5, la sortie doit être la somme de la période la plus longue qui est la somme des 5éléments, 83.

Comment une telle chose pourrait-elle être faite en utilisant c? Je suis nouveau sur C donc c'est tout ce à quoi je pouvais penser.

#include<stdio.h>
 int main() {
 int count = 0;
 int n;
 int max = 0;
 scanf("%d", &n);
 int arr[1000];
 for(int i = 0;i<n;i++){
 if(arr[i+1>arr[i])
 count++;
 if(count>max)
 max = count;
}

Solution du problème

Vous avez vraiment besoin de deux boucles.

Celui qui itère à travers tous les éléments. C'est l'index "de départ" d'une séquence.

Ensuite, une boucle interne qui commence à un élément à droite du début. Il boucle jusqu'à la fin du tableau mais s'arrête s'il voit que l'élément actuel est hors séquence.

Après la fin de la deuxième boucle, la différence de ces deux index est la longueur de la séquence.

Voici du code refactorisé. Il est annoté:

#include <stdio.h>
int arr[] = { 17, 18, 19, 5, 6, 23, 24, 25, 24, 25, 17, 18, 19 };
// show -- print a sequence
void
show(int begidx,int count,const char *tag)
{
 printf("%s: %d %d --",tag,begidx,count);
 for (; count > 0; --count, ++begidx)
 printf(" %d",arr[begidx]);
 printf("\n");
}
// sum -- get sum of the sequence
int
sum(int begidx,int count)
{
 int sum = 0;
 for (; count > 0; --count, ++begidx)
 sum += arr[begidx];
 return sum;
}
int
main(void)
{
 int count = sizeof(arr) / sizeof(arr[0]);
 int maxlen = 0;
 int maxidx = -1;
 show(0,count,"ORIG");
 // loop through all possible starting points for sequence
 for (int ilhs = 0; ilhs < count; ++ilhs) {
 int lval = arr[ilhs];
 // loop through all numbers to the right of the starter
 // stop at the array end or when we get a number that is out of sequence
 int irhs;
 for (irhs = ilhs + 1; irhs < count; ++irhs) {
 int rval = arr[irhs];
 // out of sequence -- we've hit the end
 if (rval < lval)
 break;
 lval = rval;
 }
 // get length of the sequence we just saw
 int curlen = irhs - ilhs;
 // remember a larger sequence
 if (curlen > maxlen) {
 maxlen = curlen;
 maxidx = ilhs;
 show(maxidx,maxlen,"NEW");
 }
 }
 // show the maximum sequence
 show(maxidx,maxlen,"FINAL");
 // sum the sequence
 printf("SUM: %d\n",sum(maxidx,maxlen));
 return 0;
}

Voici la sortie du programme :

ORIG: 0 13 -- 17 18 19 5 6 23 24 25 24 25 17 18 19
NEW: 0 3 -- 17 18 19
NEW: 3 5 -- 5 6 23 24 25
FINAL: 3 5 -- 5 6 23 24 25
SUM: 83

METTRE À JOUR:

Une accélération [considérable] pour ce qui précède consiste à changer :

for (int ilhs = 0; ilhs < count; ++ilhs) {

Dans:

for (int ilhs = 0; ilhs < count; ilhs = irhs) {

Et, déplacez le int irhs;au-dessus de la boucle extérieure.

Cela réduit le temps de O(n^2) à O(n)