%LuaLaTeX
\documentclass[12pt]{article}

\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}

\begin{document}


{\bf \large Задача МАКСИМАЛНА ПЕЧАЛБА}

%\begin{wrapfigure}{r}{0.25\textwidth}
%\begin{adjustbox}{width=0.25\textwidth}
%		\includegraphics{fig.jpg}
%\end{adjustbox}
%\end{wrapfigure}

\bigskip

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

\bigskip

{\bf Бавно решение}

Прочитаме в масива {\tt prices[]} дадената редица.
С двоен цикъл изчерпваме всички възможни двойки дни (за покупка и продажба) и 
намираме най-голямата разлика на цените от масива {\tt prices}:
\begin{verbatim}
for (int i = 0; i < n - 1; i++) 
  for (int j = i + 1; j < n; j++)
    res = max(res, prices[j] - prices[i]);
cout << res << endl;
\end{verbatim}

\bigskip

{\bf Бързо решение}

Използваме единичен цикъл и на всяка стъпка поддържаме намерения
до момента мининум {\tt m} на цената  и едновременно поддържаме
намерената до момента най-голяма разлика {\tt res} на текущата цена с текущия
минимум {\tt m}:
\begin{verbatim}
int m = prices[0], res = 0;
for (int i = 1; i < n; i++)
  {
    m = min(m, prices[i]);
    res = max(res, prices[i] - m);
  }
cout << res << endl;
\end{verbatim}

\bigskip

{\bf Бързо решение с малко памет}

Забелязваме, че в единичния цикъл на бързото решение използаваме пос\-ледователно 
и еднократно стойностите от масива {\tt prices[]}. Това означава, че може да нямаме 
масив в програмата, а да четем от входа тези последователни стойности. 
Така липсата на голям масив намалява значително паметта: 

\begin{verbatim}
int m; cin >> m; int res = 0;
for (int i = 1; i < n; i++)
 {
  int p; cin >> p; m=min(m,p); res=max(res, p-m);
 }
cout << res << endl;
\end{verbatim}

\hfill {\it Зорница Дженкова}
	
\end{document}
