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

const fi='';
      fo='';
      maxn=30000;
var t,i,j,re,n,lx,rx:longint;
    a,l,r:array[1..maxn] of longint;

procedure pr;
var i,j:longint;
begin
     l[1]:=1; r[n]:=n;
     for i:=2 to n do
         if a[i]>a[i-1] then l[i]:=i
         else
         begin
              for j:=l[i-1] downto 1 do
                  if a[j]<a[i] then break;
              if a[j]<a[i] then l[i]:=j+1 else l[i]:=j;
         end;
     for i:=n-1 downto 1 do
         if a[i]>a[i+1] then r[i]:=i
         else
         begin
              for j:=r[i+1] to n do
                  if a[j]<a[i] then break;
              if a[j]<a[i] then r[i]:=j-1 else r[i]:=j;
         end;
     re:=0;
     for i:=1 to n do
     begin
          j:=a[i]*(r[i]-l[i]+1);
          if j>=re then
          begin
               if j>re then
               begin
                    re:=j; lx:=l[i]; rx:=r[i];
               end
               else
               begin
                    if l[i]<lx then
                    begin
                         lx:=l[i]; rx:=r[i];
                    end;
               end;
          end;
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     readln(t);
     for i:=1 to t do
     begin
          readln(n);
          for j:=1 to n do read(a[j]);
          readln;
          pr;
          writeln(re,' ',lx,' ',rx);
     end;
     close(input); close(output);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<stack>
using namespace std;

int n, a[33333], l[33333], r[33333];

void testcase() {
    scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", a+i);
    stack<int> st; l[0] = 0;
    for(int i = 1; i < n; ++i) if(a[i] > a[i-1]) l[i] = i, st.push(i-1);
    else {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        l[i] = st.empty() ? 0 : st.top() + 1;
    }
    st = stack<int>(); r[n-1] = n-1;
    for(int i = n-2; i >= 0; --i) if(a[i] > a[i+1]) r[i] = i, st.push(i+1);
    else {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        r[i] = st.empty() ? n-1 : st.top() - 1;
    }
    int res = 0;
    for(int i = 1; i < n; ++i) if((r[i] - l[i] + 1) * a[i] > (r[res] - l[res] + 1) * a[res]) res = i;
    printf("%d %d %d\n", (r[res] - l[res] + 1) * a[res], l[res] + 1, r[res] + 1);
}

int main() {
    int tc; scanf("%d", &tc);
    while(tc--) testcase();
    return 0;
}

Code mẫu của ladpro98

program kagain;
uses    math;
const   fi='';
        fo='';
var     a:array[0..30001] of longint;
        left,right:array[0..30001] of longint;
        area,dau,cuoi,n,t,i,j:longint;
        inp,oup:text;
procedure openFile;
begin
        assign(inp,fi);
        reset(inp);
        assign(oup,fo);
        rewrite(oup);
end;

procedure closeFile;
begin
        close(inp);
        close(oup);
end;

procedure process;
var     i,t:longint;
begin
        area:=0;
        for i:=1 to n do
        begin
                left[i]:=0;
                right[i]:=0;
        end;
        left[1]:=0;
        for i:=2 to n do
        begin
                t:=i-1;
                while a[t]>=a[i] do
                        t:=left[t];
                left[i]:=t;

        end;

        right[n]:=n+1;
        for i:=n-1 downto 1 do
        begin
                t:=i+1;
                while a[t]>=a[i] do
                        t:=right[t];
                right[i]:=t;

        end;

        for i:=1 to n do
        begin
                if area<((right[i]-left[i]-1)*a[i]) then
                begin
                        area:=(right[i]-left[i]-1)*a[i];
                        dau:=left[i]+1;
                        cuoi:=right[i]-1;
                end;
        end;
end;

begin
        openFile;
        readln(inp,t);
        for i:=1 to t do
        begin
                readln(inp,n);
                for j:=1 to n do read(inp,a[j]);
                process;
                writeln(oup,area,' ',dau,' ',cuoi);
        end;
        close(oup);
end.

Code mẫu của RR

var
  a,left,right,stack:array[0..30111] of longint;
  tmp,i,n,test,top:longint;
  lr,lu,lv:longint;

begin
  read(test); a[0]:=0;
  for test:=1 to test do
    begin
      read(n);
      for i:=1 to n do read(a[i]);

      lr:=0;

      top:=0; stack[0]:=0;
      for i:=1 to n do
        begin
          while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
          left[i]:=stack[top]+1;
          inc(top); stack[top]:=i;
        end;

      top:=0; stack[0]:=n+1; a[n+1]:=a[0];
      for i:=n downto 1 do
        begin
          while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
          right[i]:=stack[top]-1;
          inc(top); stack[top]:=i;
        end;

      for i:=1 to n do
        begin
          tmp:=a[i]*(right[i]-left[i]+1);
          if (tmp>lr) or ((tmp=lr) and (left[i]<lu)) then
            begin
              lr:=tmp;
              lu:=left[i];
              lv:=right[i];
            end;
        end;

      writeln(lr,' ',lu,' ',lv);
    end;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long T,n,a[30001],left[30001],right[30001],r[30002],l[30002];
scanf("%ld",&T);
for(long i=1;i<=T;i++)
  {
  long max=0,x,y;
  scanf("%ld",&n);
  for(long j=1;j<=n;j++)
    scanf("%ld",&a[j]);
  long u=1;
  r[1]=1;
  while(r[u]!=n+1)
    {
    long t=r[u]+1;
    if(a[t]<a[r[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[r[j]])
          {
          right[r[j]]=t-1;
          u--;
          }
        else  
          break;
        }
      u++;
      r[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        right[r[j]]=n;          
      break;
      }
    else
      {
      u++;
      r[u]=t;
      }
    }            
  right[n]=n;
  u=1;
  l[1]=n;
  //printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]);
  while(l[u]!=0)
    {
    long t=l[u]-1;
    if(a[t]<a[l[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[l[j]])
          {
          left[l[j]]=t+1;
          u--;
          }
        else  
          break;
        }
      u++;
      l[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        left[l[j]]=n;          
      break;
      }
    else
      {
      u++;
      l[u]=t;
      }
    }
  left[1]=1;  
  //printf("%ld %ld %ld",left[4],left[3],left[2]);              
  for(long j=1;j<=n;j++)
    if(a[j]*(right[j]-left[j]+1)>max)
      {
      max=a[j]*(right[j]-left[j]+1);
      x=left[j];
      y=right[j];
      }             
  printf("%ld %ld %ld\n",max,x,y);
  }
//getch();
}

Code mẫu của ll931110

Program KAGAIN;
        Const
                input  = '';
                output = '';
        Var
                  a,left,right,stack: array[1..30000] of longint;
                           t,n,i,top: longint;
                               fi,fo: text;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Procedure push(x: longint);
          Begin
                inc(top);
                stack[top]:= x;
          End;

Procedure solveleft;
          Var
                i: longint;
          Begin
                top:= 1;
                stack[top]:= 1;

                left[1]:= 1;
                For i:= 2 to n do
                        Begin
                                While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
                                If top = 0 then left[i]:= 1 else left[i]:= stack[top] + 1;

                                push(i);
                        End;
          End;

Procedure solveright;
          Var
                i: longint;
          Begin
                top:= 1;
                stack[top]:= n;

                right[n]:= n;
                For i:= n - 1 downto 1 do
                        Begin
                                While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
                                If top = 0 then right[i]:= n else right[i]:= stack[top] - 1;

                                push(i);
                        End;
          End;

Procedure solve;
          Var
                kq,i,x,y: longint;
          Begin
                Readln(fi, n);
                For i:= 1 to n do read(fi, a[i]);
                Readln(fi);

                solveleft;
                solveright;

                x:= left[1];
                y:= right[1];
                kq:= (y - x + 1) * a[1];

                For i:= 2 to n do
                        if kq < (right[i] - left[i] + 1) * a[i] then
                                Begin
                                        kq:= (right[i] - left[i] + 1) * a[i];
                                        x:= left[i];
                                        y:= right[i];
                                End;

                Writeln(fo, kq, ' ', x, ' ', y);
          End;

Begin
        openfile;
                Readln(fi, t);
                For i:= 1 to t do solve;

        closefile;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   33333
int a[MAX];
int stack[MAX];
int l[MAX];
int r[MAX];
int size;
int n,c,t;
int max,f,e;
void process(void)
{
     scanf("%d",&n);
     int i;
     for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
     l[1]=1;
     size=0;
     for (i=2;i<=n;i=i+1)
         {
          if (a[i]>a[i-1])
             {
              l[i]=i;
              size++;
              stack[size]=i-1;
             }
          else
              {
               while ((size>0) && (a[stack[size]]>=a[i])) size--;              
               if (size==0) l[i]=1;
               else l[i]=stack[size]+1;
              }
         }
     r[n]=n;
     size=0;
     for (i=n-1;i>=1;i=i-1)
         {
          if (a[i]>a[i+1])
             {
              r[i]=i;
              size++;
              stack[size]=i+1;              
             }
          else
              {
               while ((size>0) && (a[stack[size]]>=a[i])) size--;
               if (size==0) r[i]=n;
               else r[i]=stack[size]-1;
              }
         }
     max=0;
     for (i=1;i<=n;i=i+1)
         {
          if (max==a[i]*(r[i]-l[i]+1))
             {
              if (l[i]<f)
                 {
                  f=l[i];
                  e=r[i];
                 }                 
             }
          if (max<a[i]*(r[i]-l[i]+1))
             {
              max=a[i]*(r[i]-l[i]+1);
              f=l[i];
              e=r[i];
             }
         }     
     printf("%d %d %d\n",max,f,e);
}
int main(void)
{
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) process();
}

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

class MaxArmy {
    public String getMax(int[] a) {
        int[] l, r;
        int n = a.length;
        l=new int[n];
        r=new int[n];
        for(int i=0;i<n;++i) {
            int x = i-1;
            while( (x>=0) && (a[x]>=a[i]) ) x = l[x] ;
            l[i] = x;
        }
        for(int i=n-1;i>=0;--i) {
            int x = i+1;
            while( (x<n) && (a[x]>=a[i]) ) x = r[x] ;
            r[i] = x;
        }
        int max=-1, left=0, right=0;
        for(int i=0;i<n;++i) {
            int x = a[i]*(r[i]-l[i]-1);
            if(x>max) {
                max=x;
                left = l[i] + 2;
                right = r[i];
            }
            else if(x==max && left>l[i]+2) {
                left = l[i] + 2;
                right = r[i];
            }
        }
        return Integer.toString(max) + " " + Integer.toString(left) + " " + Integer.toString(right);
    }
}

public class Main{
    public static void main(String[] Args) throws Exception {
        BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        int tt = parseInt(kb.readLine());
        for(int i=0;i<tt;++i) {
            int n = parseInt(kb.readLine());
            StringTokenizer st=new StringTokenizer(kb.readLine());
            int[] a=new int[n];
            for(int j=0;j<n;++j) 
                a[j] = parseInt(st.nextToken());
            System.out.println( new MaxArmy().getMax(a) );
        }
    }
}