[C] Tìm dãy số tăng dài nhất

[langtuphidao]

Bạn nào có thể share mình thuật giãi bài: tìm dãy số tăng dài nhất ko?
Vd: có 1 dãy số 5 4 3 4 7 9 0 1
thì dãy tăng dài nhất là 4 7 9

[kidteam]

bài này dùng quy hoạch động
bài trên của bạn ví dụ bị sai rồi
độ dài dãy con là 4
và dãy con o đây là dãy 3 4 7 9
dữ liệu vào từ file dayso.txt
dòng đầu chứa số lượng số n
dòng 2 chứa n số
dữ liệu ra file daycon.txt
dòng đầu chứa độ dài dãy
dòng 2 chứa kết quả

#include <stdio.h>
#include <conio.h>
int n;
int a[1002],l[1002],trace[1002];
void nhap(void);
void xuly(void);
void xuat(void);
int main(void)
  {
    nhap();
    xuly();
    xuat();
  }
void nhap(void)
  {
    FILE *f;
    f=fopen("dayso.txt","rt");
    fscanf(f,"%i",&n);
    for(int i=1;i<=n;++i)
      fscanf(f,"%i",&a[i]);
    fclose(f);
    a[0]=-10000;
    a[n+1]=10000;
  } 
void xuly(void)
  {
    int i,j,jmax;
    l[n+1]=1;
    for(i=n;i>=0;--i)
      {
        jmax=n+1;
        for(j=i+1;j<=n;++j)
          if(l[j]>l[jmax]&&a[j]>a[i])
            jmax=j;
        l[i]=l[jmax]+1;
        trace[i]=jmax;
      }
  }
void xuat(void)
  {
    FILE *f;
    f=fopen("daycon.txt","wt");
    fprintf(f,"%i\n",l[0]-2);
    int t;
    t=trace[0];
    while(t!=n+1)
      {
        fprintf(f,"%i ",a[t]);
        t=trace[t];
      }
    fclose(f);
  }
file đầu vào
dayso.txt
8
5 4 3 4 7 9 0 1
file ra 
daycon.txt
4
3 4 7 9

[ptaminh]

Thực ra bài này chỉ cần chạy 1 vòng lặp là đủ. Độ phức tạp luôn luôn bằng 0(n)

        // tim day tang dai nhat
        // s la chi so bat dau cua day trong mang a
        // len la chie dai cua day tang

        void DayTangDaiNhat(int a[],int n, int& s,int& len )
        {
            int i,j;
            int e =0;            
            len = n > 0;           

            for(i = 0,j = i; j < n ; j++)
            {     
                if(j + 1 == n -1 || a[j] >= a[j+1]) // tim day tang
                {
                    if( j - i > len )        
                    {
                        s = i;                       
                        len = j - s;
                    }
                    i = j+1;
                }
            } 
        }

[xelnaga]

anh có thể giải thích cho em cái thuật toán trên được ko ạ.
Em làm thế này nhưng mà nó ko ra

for(i = 1; i < n; i++) 
{
    count = 0;
    while (num***91;i-1***93; < num ***91;i***93; && i < n)
    {
        count++;
        i++;
    }
    if (count > max)
    {
        max = count;
        temp = i - count;        
        }
}

for (i = temp; i < temp + max; i++)
     printf("%d ", num***91;i***93;); 

[ptaminh]

ý tưởng thì cũng đơn giản thôi

Cần hai biến để xác định vị trí của dãy tìm được
ở đây là vị trí bắt đầu và chiều dài.

chạy vòng for đến khi nào phát hiện ra nghịch thế, tức là vừa tìm được một dãy thỏa dk.
ghi nhận lại độ dài lớn nhất và vị trí sau khi đem so sánh với độ dài của dãy cũ.

rồi lại tiếp tục tìm từ vị trí xảy ra nghịch thế đến hết dãy.

[xelnaga]

ý tưởng của em cũng là vậy. Nhưng em dùng vòng lặp for cả while như trên thì ko được

[hoatpm_dtu]

#include<conio.h>
#include<iostream.h>
#include<math.h>
#include<stdio.h>
void docfile(char*tenfile,int M[],int &n)
{ FILE*f; n=0;
f=fopen(tenfile,"r");
if(f!=NULL)
{ while(!feof(f))
{ int x;
fscanf(f,"%d",&x);
n++;
M[n]=x;
}
fclose(f);
}
}
void Mangcondainhat(int M[],int n)
{
int imax=0,idem,inho;
for(int i=1;i<=n;i++)
{ if(M[i]>M[i-1])
{
idem++;
if(idem>imax)
imax=idem;
inho=i;
}
else
idem=1;
}
cout<<"\n\n Mang con dai nhat co "<<imax<<" gia tri";
cout<<"\n\n Tu vi tri thu "<<inho-imax+1<<" --> "<<inho;
cout<<"\n\n Ket qua : ";
for(int j=inho-imax+1;j<=inho;j++)
{ cout<<M[j]<<" "; }
}
void main()
{ clrscr();
int M[100],n;
cout<<"\n\tKiem tra mang con tang dai nhat";
docfile("songuyen.txt",M,n);
Mangcondainhat(M,n);