fork download
copy 
  1. program mountain;
  2. Uses sysutils, Math;
  3.  
  4. const
  5.     MAXN = 100005;
  6.  
  7. var
  8.     ANS, N, i, j,h, maxMountainLength, lung : LongInt;
  9.     P, leftLIS, rightLIS  : Array[0..MAXN-1] of LongInt;
  10.     rimossi : string;
  11.     rimosso: boolean;
  12. begin
  13.  
  14.  
  15.  
  16.     ReadLn(N);
  17.     rimossi:=''; lung:=N;
  18.     for i:=0 to N-1 do begin
  19.                         Read(P[i]);
  20.                         rimossi:=rimossi+IntTostr(P[i]);
  21.                        end;  
  22.     ReadLn();
  23.     for i:=1 to lung do  write(rimossi[i],'  '); writeln;
  24.     rimosso:=false; i:=2; h:=1;
  25.     while h<5 do 
  26.        begin
  27.         i:=2; rimosso:=false;
  28.         while i<lung do
  29.               begin
  30.                 if  (rimossi[i]<rimossi[i-1]) and (rimossi[i]<rimossi[i+1]) then
  31.                                                                               begin
  32.                                                                                 delete(rimossi,i,1);
  33.                                                                                 lung:=lung-1;
  34.                                                                                 rimosso:=true;
  35.                                                                               end;
  36.               i:=i+1;
  37.               end;
  38.            h:=h+1;   
  39.          end;     
  40.     for i:=1 to lung  do begin  P[i-1]:=StrToInt(rimossi[i]); write(P[i-1],' ');end;
  41.      end. 
  42.     ANS := 0; 
  43. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  44. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  45.  
  46.    for i:=0 to  N-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; rimosso[i]:=0; end;
  47.  
  48. 	(*Calculate LIS from left to right for each position*)
  49.    for i:=1 to N-2 do if  (P[i]<P[i-1]) and (P[i]<P[i+1]) then rimosso[i]:=1; 
  50.    for i := 1 to N-1 do
  51.          if (rimosso[i]=0) then 
  52.              for j:= 0 to i-1 do
  53.                 begin
  54.                   if (rimosso[j]=0) and (P[i] > P[j]) then leftLIS[i] := max(leftLIS[i], leftLIS[j] + 1);                          
  55.                 end;  
  56.  
  57. 	(* Calculate LIS from right to left (decreasing subsequence) for each position*)
  58.  
  59.    for i := N - 2 downto 0 do
  60.         if (rimosso[i]=0) then 
  61.             for  j := i + 1 to N-1 do
  62.                begin
  63.                 if (rimosso[j]=0) and (P[i] > P[j]) then rightLIS[i] := max(rightLIS[i], rightLIS[j] + 1);                
  64. 	       end;
  65.  
  66.         (* Find the maximum length of mountain subsequence*)
  67.    maxMountainLength := 0;
  68.    for i := 0 to N-1 do
  69. 	(*A valid mountain peak must have at least one element on both sides*)
  70. 	(*leftLIS[i] > 1 ensures there's at least one element before peak*)
  71. 	(*rightLIS[i] > 1 ensures there's at least one element after peak*)
  72.    if (leftLIS[i] >= 1) and (rightLIS[i] >= 1)  then
  73.   	(*Total mountain length with peak at i Subtract 1 because peak is counted in both leftLIS and rightLIS*)
  74.          maxMountainLength := max(maxMountainLength, leftLIS[i] + rightLIS[i] - 1);
  75.  	(* Minimum removals = total elements - maximum mountain length*)
  76.    ANS:= N - maxMountainLength; 
  77.    WriteLn(ANS);
  78. end.
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
6
4 3 5 1 0 2
stdout
copy 
4  3  5  1  0  2  
4 5 2
https://ideone.com/wU4dnS
language:
Pascal (fpc 3.0.4)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!