fork download
copy 
  1. program mountain;
  2. Uses Math;
  3. const
  4.     MAXN = 100005;
  5.  
  6. var
  7.     ANS, N, i, j, maxMountainLength : LongInt;
  8.     P, leftLIS, rightLIS, scartato  : Array[0..MAXN-1] of LongInt;
  9.  
  10. begin
  11.  
  12.     (*assign(input,  'input.txt');  reset(input);
  13.     assign(output, 'output.txt'); rewrite(output);*)
  14.  
  15.     ReadLn(N);
  16.  
  17.     for i:=0 to N-1 do
  18.         Read(P[i]);
  19.     ReadLn();
  20.  
  21.     ANS := 0;
  22.  
  23. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  24. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  25.  
  26.    for i:=0 to  N-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; scartato[i]:=0; end;
  27.  
  28. 	(*Calculate LIS from left to right for each position*)
  29.  
  30.    for i := 1 to N-1 do
  31.             for j:= 0 to i-1 do
  32.                 begin
  33.                   if (i<N-1) and (P[i]<P[i-1]) and (P[i]<P[i+1]) then scartato[i]:=1; 
  34.                   if (j>0) and (P[j]<P[j-1]) and (P[j]<P[j+1]) then scartato[j]:=1; 
  35.                   if (scartato[i]=0) and (scartato[j]=0) and (P[i] > P[j]) then leftLIS[i] := max(leftLIS[i], leftLIS[j] + 1);                          
  36.                 end;  
  37.  
  38. 	(* Calculate LIS from right to left (decreasing subsequence) for each position*)
  39.  
  40.    for i := N - 2 downto 0 do
  41.             for  j := i + 1 to N-1 do
  42.                begin
  43.                 if (i>0) and (P[i]<P[i-1]) and (P[i]<P[i+1]) then scartato[i]:=1; 
  44.                 if (j<N-1) and (P[j]<P[j-1]) and (P[j]<P[j+1]) then scartato[j]:=1; 
  45.                 if (scartato[i]=0) and (scartato[j]=0) and (P[i] > P[j]) then rightLIS[i] := max(rightLIS[i], rightLIS[j] + 1);                
  46. 	       end;
  47.  
  48.        (* Find the maximum length of mountain subsequence*)
  49.    maxMountainLength := 0;
  50.    for i := 0 to N-1 do
  51. 	(*A valid mountain peak must have at least one element on both sides*)
  52. 	(*leftLIS[i] > 1 ensures there's at least one element before peak*)
  53. 	(*rightLIS[i] > 1 ensures there's at least one element after peak*)
  54.    if (leftLIS[i] >= 1) and (rightLIS[i] >= 1)  then
  55.   	(*Total mountain length with peak at i Subtract 1 because peak is counted in both leftLIS and rightLIS*)
  56.          maxMountainLength := max(maxMountainLength, leftLIS[i] + rightLIS[i] - 1);
  57.  	(* Minimum removals = total elements - maximum mountain length*)
  58.    ANS:= N - maxMountainLength; 
  59.    WriteLn(ANS);
  60. end.
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
3
0 1 2
stdout
copy 
0
https://ideone.com/4wB9Rj
language:
Pascal (fpc 3.0.4)
created:
20 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!