Editorial for Dãy con tăng dài nhất (bản dễ)


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
var n,i,j,re:longint;
    a,f:array[1..1002] of longint;

begin
        read(n);
        for i:=1 to n do
        begin
                read(a[i]);
                f[i]:=1;
                for j:=1 to i-1 do
                   if a[i]>a[j] then
                      f[i]:=max(f[i],f[j]+1);
                re:=max(re,f[i]);
        end;
        writeln(re);
end.

Code mẫu của happyboy99x

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n+1], f = new int[n+1];
        for( int i = 0; i < n; ++i ) {
            a[i] = scan.nextInt();
        }
        a[n++] = 100000;
        for( int i = 0; i < n; ++i ) {
            f[i] = 1;
            for( int j = 0; j < i; ++j ) {
                if (a[j] < a[i]) {
                    f[i] = Math.max(f[i], f[j]+1);
                }
            }
        }
        System.out.println(f[n-1]-1);
    }
}

Code mẫu của ladpro98

program daycontang;
const   fi = '';
        fo = '';
var     mang,f: array[0..30001] of longint;
        i,t,n:longint;
        inp,oup:text;
function find(i,j,x:longint):longint;
var     l,r,m,k:longint;
begin
        l:=i;r:=j;
        while l<=r do
           begin
              m:=(l+r) div 2;
              if mang[f[m]]<mang[x] then
                  begin
                      k:=m;
                      l:=m+1;
                  end
              else  r:=m-1;
           end;
        exit(k);
end;

procedure input;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do read(inp,mang[i]);
        close(inp);
end;

procedure output;
begin
        assign(oup,fo);
        rewrite(oup);
        write(oup,t);
        close(oup);
end;

begin
        input;
        f[1]:=1;
        t:=1;
        for i:=2 to n do
        begin
                if mang[i]<mang[f[1]] then f[1]:=i
                else if mang[i]>mang[f[t]] then
                begin
                        inc(t);
                        f[t]:=i;
                end
                else
                begin
                        f[find(1,t,i)+1]:=i;
                end;
        end;

        output;
end.

Code mẫu của RR

import sys

n = input()
a = map(int, sys.stdin.readline().split())

res = 0
l = len(a)

f = [1] * l

for i in range(0,l):
    for j in range(0,i):
        if a[j] < a[i]:
            f[i] = max(f[i], f[j] + 1)
    res = max(res, f[i])

print res

Code mẫu của hieult

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

Code mẫu của ll931110

Program LIQ;
        Const
                input  = '';
                output = '';
                   max = 1000;
        Var
                x,l: array[0..max + 1] of integer;
                  n: integer;

Procedure enter;
          Var
                 f: text;
                 i: integer;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, n);
                        For i:= 1 to n do read(f, x[i]);
                Close(f);

                x[0]:= Low(integer);
                x[max + 1]:= High(integer);
          End;

Procedure optimize;
          Var
                i,j,jmax: integer;
          Begin
                l[n + 1]:= 1;
                For i:= n downto 0 do
                        Begin
                                jmax:= n + 1;
                                For j:= i + 1 to n + 1 do
                                        If (x[j] > x[i]) and (l[j] > l[jmax]) then jmax:= j;
                                l[i]:= l[jmax] + 1;
                        End;
          End;

Procedure printresult;
          Var
                f: text;
          Begin
                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, l[0] - 2);
                Close(f);
          End;

Begin
        enter;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
using namespace std;

const int maxn = 3e4 + 4;
long int n, a [maxn], lis [maxn], t [maxn], p;

int main (void) 
{
    scanf ("%d", &n);
    a [0] = -1e9;
    a [n + 1] = 1e9;

    for (int i = 1; i <= n + 1; ++i) {
        if (i <= n) scanf ("%ld", &a [i]);
        int l = 0, r = p;
        while (l < r) {
            int m = (l + r + 1) / 2;
            if (a [t [m]] < a [i]) l = m;
            else r = m - 1;
        }
        lis [i] = l + 1;
        if (lis [i] > p) t [++p] = i;
        else if (a [i] < a [t [lis [i]]]) t [lis [i]] = i;
    }
    printf ("%ld\n", lis [n + 1] - 1);
    return 0;
}

Code mẫu của khuc_tuan

n = input()
a = [int(x) for x in raw_input().split()]
f = []
r = 0
for i in range(n):
    t = 1
    for j in range(len(f)):
        if a[j]<a[i]: t= max(f[j]+1,t)
    f.append(t)
    r = max(t,r)
print r

Comments

Please read the guidelines before commenting.


There are no comments at the moment.