%LuaLaTeX
\documentclass[12pt]{article}
\usepackage{geometry}
\geometry{
	paper=a4paper,
	top=4cm, % Top margin
	bottom=2cm, % Bottom margin
	left=2cm, % Left margin
	right=2cm, % Right margin
	%headheight=3cm, % Header height
	%footskip=1.5cm, % Space from the bottom margin to the baseline of the footer
	%headsep=0.5cm, % Space from the top margin to the baseline of the header
	%showframe, % Uncomment to show how the type block is set on the page
}
\usepackage[T2A]{fontenc}
\usepackage[bulgarian]{babel}
\usepackage{fontspec}
\setmainfont{Times New Roman}
\setsansfont{Times New Roman}
\setmonofont{Courier New}
\usepackage[math-style=TeX]{unicode-math}
\setmathfont{Latin Modern Math}
\usepackage{hyperref}


\begin{document}

{\bf Задача РАЗЛИКА}

\bigskip


{\bf Пояснение към решенията}

\bigskip

{\bf Бавно решение}  ({\tt dif\_21p.cpp})

\medskip

Елементите на дадената редица се прочитат в масива {\tt a[i]}.
В двоен цикъл се пробягват всички двойки елементи от разглеждания
вид и в променливата {\tt r} се пресмята максималната разлика:
\begin{verbatim}
    int r=0;
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
     if(a[j]>a[i]) r=max(r,a[j]-a[i]);
\end{verbatim} 
Накрая се отпечатва стойността на {\tt r}.


\bigskip

{\bf Бързо решение}  ({\tt dif\_57p.cpp})

\medskip

Обхождаме последователно елементите на дадената редица и 
поддържаме във всеки момент две стойности:

--	в променливата {\tt r} се записва най-голямата търсена разлика до момента.

--	в променливата {\tt m} се записва най-малката стойност на елемент от редицата до момента.

На всяка стъпка пресмятаме новата най-голяма разлика {\tt r} и актуализираме 
новата най-малка стойност {\tt m}. 

\begin{verbatim}
      int r = a[1] - a[0];
      int m = a[0];
      for(int i = 1; i < n; i++)
      {
         if (a[i] - m > r) r = a[i] - m;
         if (a[i] < m) m = a[i];
      }
\end{verbatim}
Накрая се отпечатва стойността на {\tt r}.

\bigskip

{\bf Бързо решение с малко памет -- 100 т.} ({\tt dif\_100p.cpp})

\medskip

В предното решение забелязваме, че само по веднъж ползваме всяка от стойностите 
на дадената редица. Така решаваме задачата с едно обхождане на дадената редица 
и не е необходимо да използване масив, което намалява големината на използваната 
памет в програмата.  Основаният фрагмент от предната програма може да променим така:
\begin{verbatim}
     cin >> n; cin >> a0 >> a;
     int r = a - a0; int m = a0;
     for(int i = 1; i < n; i++)
      {
        if (a - m > r) r = a - m;
        if (a < m) m = a;
        if(i<n-1) cin >> a;
      }
\end{verbatim}

\hfill{\it Емил Келеведжиев}

	
\end{document}