So I had to solve a problem :
given a file that contains N numbers I have to output the largest number that all numbers before it are less than it and all numbers after it are larger than it..if there is no such number the output is 'not found' !
so I wrote this code on pascal
program solar ;
uses crt,dos,sysutils;
var i,k,m,j,min,max,pos:longint;
a,mi,ma:array [1..1000000] of longint;
filein,fileout:textfile;
hours:word;
minutes:word;
seconds:word;
sec100:word;
procedure startclock;
begin
gettime(hours,minutes,seconds,sec100);
end;
procedure stopclock;
var seconds_count:longint;
c_hours:word;
c_minutes:word;
c_seconds:word;
c_sec100:word;
mil:longint;
begin
gettime(c_hours,c_minutes,c_seconds,c_sec100);
seconds_count:=(c_seconds-seconds)* 100 +(c_minutes-minutes) * 6000 + (c_hours-hours)*360000;
mil:=seconds_count+c_sec100-sec100;
writeln(mil/100:4:2,' seconds');
end;
Begin
startclock;
assign(filein,'solar.in');
reset(filein);
readln(filein,m);
i:=0;
repeat
i:=i+1;
readln(filein,a[i]);
until eof(filein);
close(filein);
ma[1]:=a[1];
mi[m]:=a[m];
for i:=2 to m do
begin
if a[i]>ma[i-1] then
begin
ma[i]:=a[i];
end
else
begin
ma[i]:=ma[i-1];
end;
end;
pos:=-1;
i:=m-1;
while i>=2 do
begin
if a[i]<mi[i+1] then
begin
mi[i]:=a[i];
end
else
begin
mi[i]:=mi[i+1];
end;
if (a[i]>ma[i-1]) and (a[i]<mi[i+1]) then
begin
pos:=a[i];
break;
end;
i:=i-1;
end;
assign(fileout,'solar.out');
rewrite(fileout);
if pos=-1 then
writeln(fileout,'NOT FOUND')
else
writeln(fileout,pos);
close(fileout);
stopclock();
readkey();
end.
when I run with an input of 80.000 numbersit takes 20 ms
but when I run this (c++) :
#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
clock_t t1,t2;
t1=clock();
ifstream fin;ofstream fout;
fin.open("solar.txt");
int x;
int arr[80000];int min[80000];int max[80000];
int result(-1);
fin>>x;
fin>>arr[0];
max[0]=arr[0];
for (int i=1;i<x;i++)
{ int temp;fin>>temp;
arr[i]=temp;
if(temp>max[i-1]) max[i]=temp; else max[i]=max[i-1];
}
min[x-1]=arr[x-1];
for (int i=x-2;i>=0;i--)
{
if(arr[i]<min[i+1]) min[i]=arr[i]; else min[i]=min[i+1];
if(arr[i]<min[i+1] && arr[i]>max[i-1]) { result=arr[i];break;}
}
fout.open("solarout.txt");
if(result==-1) fout<<"NOT FOUND"<<endl;
else
fout<<result<<endl;
t2=clock();
fin.close();fout.close();
cout<<t2-t1<<endl;
system("pause");
}
with the same input it takes 300 ms
also...I can't declare a static array with many cells on C++...if I try to declare a 1.000.000 size array like I did in pascal the program crashes...
my questions are :
1) why does this happen
2) why can't I declare big static arrays ?
3) are dynamic arrays (not linked lists vectors etc...just dynamic arrays declared using the NEW keyword ) slower than static ones (suppose I execute the same code)
4) Is there a more effective (effective=fast) way to solve this problem ?
what I do is : a) pass the numbers in an array, b) get the maximum number of a cell and the ones before it and save it an another same-sized array,c) get the minimum number of a cell and the ones after it,and check if the number in the cell meets the criteria...if it does I break the loop since i want the largest number and that means all other numbers before it are less than it...
thank you very much !