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