[Resolvido] Maior sequencia crescente

[askazy]

O objetivo do programa é encontrar o tamanho da maior subsequencia crescente, dado uma sequência de tamanho n:

exemplo:

Entrada 8 4 1 2 3 0 5 7 8

Saída: 4

O número 8 representa o tamanho da sequência. Não sei porque não está dando certo.

#include <stdio.h>
int main (){
  int n,i,vet[50],cont=1,maior=0;
     scanf ("%d",&n);
     for (i=0;i<n;i++) scanf ("%d",&vet[i]);
     for (i=1;i<n;i++){
         if (vet[i] > vet[i-1])
             cont++;
         else{
             if (cont > maior)
                 maior = cont;

             cont=1;
         }
     }			  
     printf ("A maior sequencia crescente tem tamanho %d\n",maior);
     system ("pause");
     return 0;
}

[HappyHippyHippo]

eu não percebo as voltas e complicações que fazes com os exercícios

isso resolvesse com 4 linhas de código e um único ciclo (se bem que pensando bem seria desnecessário).

volta a ler o problema e pensa melhor em como resolver

[Warrior]

Pensa quando é que estás a copiar o contador para a variável maior. Em que situações é que isso pode dar a resposta errada? Não acho que o código esteja assim tão confuso, mas ter identação correcta ajudava imenso.

[HappyHippyHippo]

não é o código que é confuso mas sim a resolução do problema

[askazy]

Ah percebi o problema, ele só copiava a variável cont para o maior caso ele chegasse em um que quebra da sequencia, então se eu tivesse uma sequência infinita maior ele ia pegar a última sequência maior que teve uma quebra. Não sei se é a melhor solução mas ai está.

#include <stdio.h>
int main ()
{
 int n,num,aux,cont=1,maior=0,i;
 scanf ("%d",&n);
 scanf ("%d",&aux);
 for(i=1; i<n; i++)
 {
 scanf ("%d",&num);
 if (num >aux)
 {
	 cont++;
	 if (cont>maior) maior=cont;
 }

 else
 {
	 if (cont>maior) maior=cont;
	 cont=1;
 }
 aux=num;
 }
 printf ("A maior subsequencia tem tamanho %d\n",maior);
 return 0;
}

[HappyHippyHippo]

bem ... a meu ver, como estás demasiado verde na matéria acho que o melhor é apresentar a solução a ver se aprendes com o exemplo:

#include <stdio.h>
#include <limits.h>

int main (){
 int n = 0, i = 0, count = 0, cur = 0, prev = INT_MIN;

 // saber o número de valores que serão lidos
 scanf ("%d", &n);

 // ciclo de leitura dos n valores
 while (i < n) {
   // ler o valor
   scanf (" %d", &cur);

   // se o valor lido for maio que o anterior
   if (cur > prev)
     // incrementar a contagem da sequência crescente
     count++;
   else {
     // verificar se a sequência actual é maior que a anterior
     if (max < count)
       // guardar o tamanho da sequência actual
       max = count;

     // iniciar a contagem da próxima sequência
     count = 0;
   }

   // guardar o valor lido
   prev = cur;
 }

 printf ("A maior sequencia crescente tem tamanho %d\n", max);

 return 0;
}

[askazy]

Happy o seu código usa uma estrutura com coisas que agente não aprende na disciplina. Agente não usa essa biblioteca <limits.h>. As vezes as minhas soluções não são tão boas, por causa que o curso é tipo um introdutório em linguagem C padrão, então eu só escrevo baseado no que eu aprendi.

[Warrior]

Happy: o teu bug tem o mesmo bug que o código inicial dele. Também não acho que seja mais simples.

askazy: uma forma de dares a volta ao problema que estavas a ter é, em vez de verificares se é maior que o máximo sempre que incrementas, podes adicionar uma verificação no exterior do ciclo de forma a evitar verificar todas as iterações.

[HappyHippyHippo]

Happy: o teu bug tem o mesmo bug que o código inicial dele.

sim, além de :

- count estar a ser atribuído a zero em vez de 1

- não estou a fazer a verificação final

- nem estou a incrementar o i

mas como o código foi feiro de cabeça ...

Também não acho que seja mais simples.

eu quando disse que se podia resolver com menos código era em relação a isto :

#include <stdio.h>

int main (void) {
 int n = 0, i = 0, prev = 0, cur, count, max;

 scanf ("%d", &n);
 max = count = scanf("%d", &prev);
 for (i = 1; i < n; ++i) {
   if (scanf(" %d", &cur))
     count = (cur > prev) ? (count + 1) : ((max = max > count ? max : count), 1);
   prev = cur;
 }
 max = max > count ? max : count;

 printf ("A maior sequencia crescente tem tamanho %d\n", max);
 return 0;
}

agora imagina o que seria o @askazy olhar para esta código ...

[igorduartetkd]

HappyHippiHippo sua logica está incorreta, o problema nao e tao simples como imaginastes, primeiro deves aprender o que é uma subsequencia, leia atentamente esse site que nele é explicado o problema e a resoluçao http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/sscm.html

O algoritmo para resolver é esse:

/* Igor Duarte - 08/05/2016
 * MAIOR SUBSEQUENCIA CRESCENTE MAXIMA
 * Em outras palavras, B[1..k] é uma subsequência de A[1..n] se existem índices i1,i2,…,ik tais que 1 ≤ i1 < i2 < … < ik ≤ n
 * e B[1] = A[i1], B[2] = A[i2], … , B[k] = A[ik] .
 */

#include <stdio.h>
#define maxSeq 200

int vetProgDinamica [maxSeq + 1];
int sequencia[maxSeq +1];

int main(){
  int i, j, tam, maior;
  while(scanf("%d", &tam), tam) {
    //lendo os elementos da sequnecia:
    for(i=1; i<=tam; i++){
      scanf("%d", &sequencia[i]);
    }

    //inicio da programaçao dinamica:
    for(j = 1; j <= tam; j++) {
      //com esse elemento ja tenho certeza que consigo subsequencia de tamanho 1:
      vetProgDinamica[j] = 1;
      //calculando a maior subsequencia que consigo com esse elemento:
      for( i=j-1; i > 0; i--) {
        if(sequencia < sequencia[j] && vetProgDinamica[i] + 1 > vetProgDinamica[j]) { //caso dois elementos iguais formem subsequencia mudar < para <=
          vetProgDinamica[j] = vetProgDinamica[i] + 1;
        }
      }
    }
    
    //percorrendo o vetor gerado na programaçao dinamica para encontrar a maior subsequencia:
    maior = 0;
    for(i=1; i<=tam; i++){
      if(vetProgDinamica[i] > maior){
        maior = vetProgDinamica[i];
      }
    }

    //imprimindo a maior:
    printf("%d\n", maior);
  }
}

[HappyHippyHippo]

HappyHippiHippo sua logica está incorreta

dado que o autor do tópico marcou este como resolvido, é supor que a solução apresentada está correcta o que indica que o tipo de problema difere do que apresentas aqui.

Edited May 9, 2016 by HappyHippyHippo

[igorduartetkd]

O autor pode ate ter marcado como resolvido mas o problema pode ter sido resolvido de forma equivocada. Só da uma olhada no link que postei, esse problema da subsequencia crescente maxima é classico, nao sou eu que estou resolvendo, ja foi resolvido a muitos anos.

[HappyHippyHippo]

a este tipo de problema (académicos) está associado um conjunto de testes.

se a solução apresentada não foi contradita, então é de assumir que está correcta, isto porque, novamente, aqui a unica pessoa que está a assumir o que quer que seja sem ter a informação exacta do problema, és tu.

[Jonatas Laet]

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <vector>
#include <stdio.h>
#define fori(i, n) for (int i = 0; i < (n); i++)
using namespace std;

// Longest Increasing Subsequence - LIS O(n log n)
// Fonte: http://www.maratona.dcc.ufmg.br/UFMG-TRD-2011.pdf
// Adaptado por: Jonatas Laet
void lis( const vector< int > & v, vector< int > & asw )
{
	vector<int> pd(v.size(), 0), pd_index(v.size()), pred(v.size());
	int maxi = 0, x, j, ind;
	fori(i, v.size())
	{
		x = v[i];
		j = lower_bound( pd.begin(), pd.begin() + maxi, x ) - pd.begin();
		pd[j] = x;
		pd_index[j] = i;
		if( j == maxi )
		{
			maxi++;
			ind = i;
		}
		pred[i] = j ? pd_index[j - 1] : -1;
	} // return maxi;
	int pos = maxi - 1, k = v[ind];
	asw.resize( maxi );
	while ( pos >= 0 )
	{
		asw[pos--] = k;
		ind = pred[ind];
		k = v[ind];
	}
}

int main(int argc, char *argv[])
{
	vector< int > v; //8, 4, 1, 2, 3, 0, 5, 7, 8
	vector< int > v2;
	v.push_back(8);
	v.push_back(4);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(0);
	v.push_back(5);
	v.push_back(7);
	v.push_back(8);
	lis(v, v2);
	int t = v2.size();
	//Mostrando o vetor com os valores da maior subsequencia crescente
	fori(i, t)
	{
		printf("%d ", v2[i]);
	}
	printf("\n");
	
	//Mostrando o tamanho desse vetor
	printf("%d\n", v2.size());
	
	return 0;
}

Mais informações sobre como funciona o Longest Increasing Sequence: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

[HappyHippyHippo]

10 hours ago, Jonatas Laet said:

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <vector>
#include <stdio.h>
#define fori(i, n) for (int i = 0; i < (n); i++)
using namespace std;

// Longest Increasing Subsequence - LIS O(n log n)
// Fonte: http://www.maratona.dcc.ufmg.br/UFMG-TRD-2011.pdf
// Adaptado por: Jonatas Laet
void lis( const vector< int > & v, vector< int > & asw )
{
	vector<int> pd(v.size(), 0), pd_index(v.size()), pred(v.size());
	int maxi = 0, x, j, ind;
	fori(i, v.size())
	{
		x = v[i];
		j = lower_bound( pd.begin(), pd.begin() + maxi, x ) - pd.begin();
		pd[j] = x;
		pd_index[j] = i;
		if( j == maxi )
		{
			maxi++;
			ind = i;
		}
		pred[i] = j ? pd_index[j - 1] : -1;
	} // return maxi;
	int pos = maxi - 1, k = v[ind];
	asw.resize( maxi );
	while ( pos >= 0 )
	{
		asw[pos--] = k;
		ind = pred[ind];
		k = v[ind];
	}
}

int main(int argc, char *argv[])
{
	vector< int > v; //8, 4, 1, 2, 3, 0, 5, 7, 8
	vector< int > v2;
	v.push_back(8);
	v.push_back(4);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(0);
	v.push_back(5);
	v.push_back(7);
	v.push_back(8);
	lis(v, v2);
	int t = v2.size();
	//Mostrando o vetor com os valores da maior subsequencia crescente
	fori(i, t)
	{
		printf("%d ", v2[i]);
	}
	printf("\n");
	
	//Mostrando o tamanho desse vetor
	printf("%d\n", v2.size());
	
	return 0;
}

Mais informações sobre como funciona o Longest Increasing Sequence: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

é sempre "interesante" apresentar uma solução em C++ na secção de C ...