{"id":353966,"date":"2024-05-20T22:38:54","date_gmt":"2024-05-20T22:38:54","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=353966"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=353966","title":{"rendered":"<span>\u0412\u044b\u0432\u043e\u0434 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u043c\u0430 \u0411\u0451\u0440\u0434\u0430-\u041c\u0435\u0435\u0440\u0442\u0435\u043d\u0441\u0430<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0438\u0437 \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445, \u043f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u043c\u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0411\u0451\u0440\u0434 \u0438 \u041c\u0435\u0435\u0440\u0442\u0435\u043d\u0441 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 <a href=\"https:\/\/academic.oup.com\/comjnl\/article\/32\/2\/122\/543545?login=false\" rel=\"nofollow noopener noreferrer\">\u0444\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u043c<\/a>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0432\u044b\u0441\u0448\u0435\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <code>map<\/code>, <code>fold<\/code>, <code>scan<\/code>, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u0435. (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Bird%E2%80%93Meertens_formalism\" rel=\"nofollow noopener noreferrer\">\u0421\u043c. \u0442\u0430\u043a\u0436\u0435 \u043d\u0430 \u0412\u0438\u043a\u0438<\/a>). \u041d\u0438\u0436\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0432\u043e\u043b\u044c\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u0441\u0442\u0430\u0442\u044c\u0438 \u0411\u0451\u0440\u0434\u0430.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Maximum_subarray_problem\" rel=\"nofollow noopener noreferrer\">\u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0443\u043c\u043c\u044b \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430<\/a>. \u042d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u043e\u0447\u043d\u043e\u0433\u043e \u043e\u0442\u0432\u0435\u0442\u0430:<\/p>\n<p>  <\/p>\n<blockquote><p>\u0414\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0447\u0438\u0441\u0435\u043b, \u0430 \u0437\u0430\u0442\u0435\u043c \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0442\u0430\u043a\u0438\u0445 \u0441\u0443\u043c\u043c \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e.<\/p><\/blockquote>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<p>\u0422\u0430\u043a\u0430\u044f \u0441\u043b\u043e\u0432\u0435\u0441\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0435\u0443\u0434\u043e\u0431\u043d\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u043c\u0430\u043d\u0438\u043f\u0443\u043b\u044f\u0446\u0438\u0439. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u0432\u0435\u0434\u0451\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>segs<\/code> \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u044b (\u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u044b) \u043c\u0430\u0441\u0441\u0438\u0432\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def segs(input: Array[Int]): List[Array[Int]] = ???<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">segs :: [Int] -> [[Int]]<\/code><\/pre>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>sum<\/code> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0441\u0443\u043c\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def sum(input: Array[Int]): Int = input.sum<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">sum :: [Int] -> Int<\/code><\/pre>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0441\u0443\u043c\u043c\u044b, \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043a \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>sum<\/code>. \u0422\u0430\u043a\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 <code>map<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def map[A, B](f: A => B)(list: List[A]): List[B] = list.map(f)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">map :: (a -> b) -> [a] -> [b]<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0443\u043c\u043c\u0443, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>max<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def max(lst: List[Int]): Int = lst.max<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">max :: [Int] -> Int<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0443\u044e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, <code>mss<\/code> (&#171;max segment sum&#187;). \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0432\u0438\u0434:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def mss(arr: Array[Int]): Int = max(map(sum)(segs(arr)))<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss :: [Int] -> Int mss arr = max(map(sum)(segs(arr)))<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 Haskell&#8217;\u0435 \u043c\u043e\u0436\u043d\u043e \u0442\u0443 \u0436\u0435 \u0441\u0430\u043c\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u0435\u0435, \u0435\u0441\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440 \u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u0438 <code>.<\/code>. \u0422\u0430\u043a\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043e\u0434\u043d\u043e\u0433\u043e \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442 \u043f\u0440\u0430\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043a \u0441\u0432\u043e\u0435\u043c\u0443 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0443, \u0430 \u0437\u0430\u0442\u0435\u043c \u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043a \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0443, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0451\u043d\u043d\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439. \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, <code>f . g<\/code> \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e <code>x => f(g(x))<\/code>.<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map(sum) . segs<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0441\u043a\u043e\u0431\u043e\u0447\u043a\u0438, \u0442.\u043a. \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b \u043f\u0435\u0440\u0435\u0434\u0430\u044e\u0442\u0441\u044f \u0438 \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map sum . segs<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 Scala \u0432\u043c\u0435\u0441\u0442\u043e <code>.<\/code> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <code>compose<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(sum) `compose` segs<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043e\u043a \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0438 \u0432 \u0442\u043e \u0436\u0435 \u0432\u0440\u0435\u043c\u044f \u0434\u0430\u0451\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0451 \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u043c\u0435\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <code>O(n^3)<\/code> \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 <code>O(n^2)<\/code> \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>\u0412\u0441\u043b\u0435\u0434 \u0437\u0430 \u0411\u0451\u0440\u0434\u043e\u043c \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n<p>  <\/p>\n<h2 id=\"opredelenie-segs\">\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 <code>segs<\/code><\/h2>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0432\u0441\u0435 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u044b \u043c\u043e\u0436\u043d\u043e \u0432 \u0434\u0432\u0430 \u043f\u0440\u0438\u0451\u043c\u0430. \u0412\u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043d\u0430\u0447\u0430\u043b\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 (<code>inits<\/code>). \u0410 \u0437\u0430\u0442\u0435\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u0439\u0442\u0438 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u044f (<code>tails<\/code>).<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def inits(arr: Array[Int]): List[Array[Int]] = ??? def tails(arr: Array[Int]): List[Array[Int]] = ???<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">inits :: [Int] -> [[Int]] tails :: [Int] -> [[Int]]<\/code><\/pre>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c <code>tails<\/code> \u043a \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u043d\u0430\u0447\u0430\u043b\u0443, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 <code>map<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">segs1 :: [Int] -> [[[Int]]] segs1 arr = map(tails)(inits(arr)) segs1 = map tails . inits<\/code><\/pre>\n<p>  <\/p>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043f\u0438\u0441\u043a\u043e\u0432 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0441\u043a\u043b\u0435\u0438\u043c \u0432\u0441\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>concat<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">concat :: [[a]] -> [a]<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">def concat[A](lst2: List[List[A]]): List[A] = lst2.flatten<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0444\u0443\u043d\u043a\u0446\u0438\u044f <code>segs<\/code> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">segs = concat . map tails . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val segs = concat `compose` map(tails) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0441\u0442\u0430\u0432\u0438\u0432 \u044d\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map sum . concat . map tails . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(sum) `compose` concat `compose` map(tails) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"raspredelenie-map-vnutri-vlozhennyh-spiskov-map-promotion\">\u0420\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 <code>map<\/code> \u0432\u043d\u0443\u0442\u0440\u0438 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432 (map promotion)<\/h2>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u0435\u043c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438, \u0430 \u0437\u0430\u0442\u0435\u043c \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0442\u043e \u043c\u044b \u0441 \u0442\u0435\u043c \u0436\u0435 \u0443\u0441\u043f\u0435\u0445\u043e\u043c \u043c\u043e\u0436\u0435\u043c \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u0430 \u0443\u0436\u0435 \u0437\u0430\u0442\u0435\u043c \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u0442\u044c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0431\u0443\u0434\u0435\u0442 \u0442\u0435\u043c \u0436\u0435.<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u043d\u0443\u0442\u0440\u0438 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u043d\u0430\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0434\u0432\u0430\u0436\u0434\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <code>map<\/code>. \u041e\u0434\u0438\u043d \u0440\u0430\u0437 \u0434\u043b\u044f \u0432\u043d\u0435\u0448\u043d\u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430, \u0430 \u043f\u043e\u0442\u043e\u043c, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0433\u043e.<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def mapconcat[A, B](f: A => B)(lst2: List[List[A]]): List[B] =    lst2.map(innerList => innerList.map(f)).flatten def mapconcat2[A, B](f: A => B)(lst2: List[List[A]]): List[B] =    lst2.flatten.map(f)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">mapconcat f lst2 = concat(map(map(f))(lst2)) mapconcat f = concat . map(map(f)) mapconcat f = concat . map (map f)  mapconcat2 f lst2 = map(f) (concat(lst2)) mapconcat2 f = map(f) . concat<\/code><\/pre>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u0434\u0432\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u0430\u044e\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0422\u043e \u0435\u0441\u0442\u044c \u043e\u043d\u0438 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b. \u0411\u0443\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u043e\u0434\u0430 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c <code>\u2261<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">map(f) . concat \u2261 concat . map(map f) <\/code><\/pre>\n<p>  <\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u044d\u0442\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c <code>mss<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map sum . concat . map tails . inits mss = max . concat . map (map sum) . map tails . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(sum) `compose` concat `compose` map(tails) `compose` inits val mss: Array[Int] => Int =      max `compose` concat `compose` map(map(sum)) `compose` map(tails) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"raspredelenie-max-po-vlozhennym-spiskam-s-ispolzovaniem-raspredelitelnogo-svoystva-concatfold-fold-promotion\">\u0420\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 <code>max<\/code> \u043f\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u0430\u043c \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <code>concat<\/code>\/<code>fold<\/code> (fold promotion)<\/h2>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>max<\/code>, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0430\u044f \u0432\u044b\u0448\u0435, \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u043e\u0439. \u041e\u043d\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043d\u0430 \u0432\u0445\u043e\u0434 \u0441\u043f\u0438\u0441\u043e\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0442\u043e\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0443 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0422\u0430\u043a\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u0442\u044c \u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u043e\u0439 <code>\u22cf<\/code> (\u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0435\u0440\u043c\u0438\u043d &#171;\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f <code>max<\/code>&#171;, \u0447\u0442\u043e\u0431\u044b \u0431\u044b\u043b\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u0435\u0435). \u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>max<\/code>, \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0449\u0430\u044f \u043d\u0430 \u0432\u0445\u043e\u0434 \u0441\u043f\u0438\u0441\u043e\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>max<\/code> \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u0432\u0451\u0440\u0442\u043a\u0438 <code>foldl<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">max = foldl(\u22cf)(-\u221e)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">def max(lst: List[Int]): Int =   lst.foldLeft(Int.MinValue)(math.max)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f <code>max<\/code> \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438. \u041c\u043e\u0436\u043d\u043e \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c <code>max<\/code> \u0434\u043b\u044f \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u0430 \u043f\u043e\u0442\u043e\u043c \u0443\u0436\u0435 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c <code>max<\/code> \u0434\u043b\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432. \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">max . concat \u2261 max . map(max)<\/code><\/pre>\n<p>  <\/p>\n<p>(\u0417\u0434\u0435\u0441\u044c \u043c\u044b \u0441\u0440\u0430\u0437\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u0438 <code>\u2261<\/code>.)<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def maxConcat(lst2: List[List[Int]]): Int =    max(concat(lst2)) def maxConcat2(lst2: List[List[Int]]): Int =    max(lst2.map(innerList => max(innerList)))<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0435 \u0436\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0434\u043b\u044f \u043b\u044e\u0431\u044b\u0445 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0441\u043a\u043b\u0435\u0439\u043a\u0438 \u0441\u043f\u0438\u0441\u043a\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u044d\u0442\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c <code>mss<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . concat  . map (map sum) . map tails . inits mss = max . map max . map (map sum) . map tails . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` concat `compose` map(map(sum)) `compose` map(tails) `compose` inits val mss: Array[Int] => Int =      max `compose` map(max) `compose` map(map(sum)) `compose` map(tails) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"distributivnyy-zakon-dlya-map-i-compose-sliyanie-ciklov\">\u0414\u0438\u0441\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u0432\u043d\u044b\u0439 \u0437\u0430\u043a\u043e\u043d \u0434\u043b\u044f <code>map<\/code> \u0438 <code>compose<\/code> (\u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u0446\u0438\u043a\u043b\u043e\u0432)<\/h2>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u0441\u043f\u0438\u0441\u043a\u0430, \u0442\u043e \u044d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043b\u0438\u0431\u043e \u0434\u0432\u0443\u043c\u044f \u043f\u0440\u043e\u0445\u043e\u0434\u0430\u043c\u0438 <code>map<\/code> \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u044e\u0442\u0441\u044f <code>compose<\/code>, \u043b\u0438\u0431\u043e \u043e\u0434\u043d\u0438\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u043e\u043c, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0441\u043a\u043b\u0435\u0435\u043d\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">map f . map g \u2261 map (f . g)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u0434\u043b\u044f <code>mss<\/code> \u0443 \u043d\u0430\u0441 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0442\u0440\u0438 \u043f\u043e\u0434\u0440\u044f\u0434 <code>map<\/code>&#8216;\u0430. \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u043b\u0435\u0438\u0442\u044c \u0432\u0441\u0435 \u0442\u0440\u0438:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">map max . map (map sum) . map tails \u2261 map (max . (map sum) . tails)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0432\u0435\u0440\u0441\u0438\u044e <code>mss<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map max . map (map sum) . map tails . inits mss = max . map (max . (map sum) . tails)       . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(max) `compose` map(map(sum)) `compose` map(tails) `compose` inits val mss: Array[Int] => Int =      max `compose` map(    max `compose` map(sum) `compose` tails      ) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"shema-gornera\">\u0421\u0445\u0435\u043c\u0430 \u0413\u043e\u0440\u043d\u0435\u0440\u0430<\/h2>\n<p>  <\/p>\n<p>\u0414\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0431\u044b\u043b\u0438 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u044b\u043c\u0438 \u0438 \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u043b\u0438 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438. \u0421\u0445\u0435\u043c\u0430 \u0413\u043e\u0440\u043d\u0435\u0440\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c \u0441\u0432\u0451\u0440\u0442\u043a\u0443 \u0441 \u0434\u0432\u0443\u043c\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u0441\u0440\u0430\u0437\u0443. <\/p>\n<p>  <\/p>\n<p>\u0412 \u0441\u0445\u0435\u043c\u0435 \u0413\u043e\u0440\u043d\u0435\u0440\u0430 \u0437\u0430\u0434\u0435\u0439\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u044b \u0434\u0432\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>\u2295<\/code>, <code>\u2297<\/code>. \u0414\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>\u2297<\/code> \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c \u043d\u0435\u0439\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u043c\u044b\u0439 <code>1<\/code>, \u043a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u0438\u0441\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u0432\u043d\u044b\u0439 \u0437\u0430\u043a\u043e\u043d \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <code>\u2295<\/code>. \u0417\u0430\u043f\u0438\u0448\u0435\u043c \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u044d\u0442\u0443 \u0441\u0445\u0435\u043c\u0443 \u0434\u043b\u044f \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ae9\/b25\/605\/ae9b25605ede848c536469e437d1568a.svg\" alt=\"$ x_1 \u2297 x_2 \u2297 x_3 \u2297 ... \u2297 x_n + x_1 \u2297 x_2 \u2297 x_3 \u2297 ... \u2297 x_{n-1} + ... + x_1 \u2297 x_2 + x_1 + 1 = \\\\ = x_1 \u2297 (x_2 \u2297 x_3 \u2297 ... \u2297 x_n + x_2 \u2297 x_3 \u2297 ... \u2297 x_{n-1} + ... + x_2 + 1) + 1 = \\\\ = x_1 \u2297 (x_2 \u2297 (x_3 \u2297 ... \u2297 x_n + x_3 \u2297 ... \u2297 x_{n-1} + ... + 1) + 1) + 1 = \\\\ = x_1 \u2297 (x_2 \u2297 (x_3 \u2297 (... (x_{n-1}\u2297(x_n + 1)) ...) + 1) + 1) + 1 $\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>\u041c\u044b \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f <code>n*(n-1)\/2<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 <code>\u2297<\/code>, \u0430 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u2014 \u0442\u043e\u043b\u044c\u043a\u043e <code>n<\/code>. \u0422.\u0435. \u0442\u0430\u043a\u0430\u044f \u0441\u0445\u0435\u043c\u0430 \u0432\u044b\u0433\u043e\u0434\u043d\u0430 \u0441 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u044d\u0442\u0443 \u0441\u0445\u0435\u043c\u0443 \u043a \u043d\u0430\u0448\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>\u2297<\/code> \u0443 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u043e\u0431\u044b\u0447\u043d\u043e\u0435 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435 (<code>+<\/code>), \u043d\u0435\u0439\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c <code>1<\/code> \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <code>0<\/code>. \u0410 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>\u2295<\/code> \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <code>\u22cf<\/code> (\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <code>max<\/code>). \u0414\u043b\u044f \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u0438\u0441\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u0432\u043d\u044b\u0439 \u0437\u0430\u043a\u043e\u043d \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>max<\/code>:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/688\/8db\/ca8\/6888dbca87aedac270bbe83d10c55bd4.svg\" alt=\"$ a + (b \u22cf c) \u2261 (a + b) \u22cf (a + c) $\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>(\u0422\u043e \u0435\u0441\u0442\u044c, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c, \u0430 \u0437\u0430\u0442\u0435\u043c \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443, \u043b\u0438\u0431\u043e \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u043d\u0442\u0441\u0442\u0430\u043d\u0442\u0443, \u0430 \u043f\u043e\u0442\u043e\u043c \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c.) \u0414\u043b\u044f \u044d\u0442\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441\u0445\u0435\u043c\u0430 \u0413\u043e\u0440\u043d\u0435\u0440\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0438\u0434:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a89\/deb\/d15\/a89debd150c43ee7fa593adc903654ba.svg\" alt=\"$ (x_1 + x_2 + x_3 + ... + x_n) \u22cf (x_1 + x_2 + x_3 + ... + x_{n-1}) \u22cf ... \u22cf (x_1 + x_2) \u22cf x_1 \u22cf 0 = \\\\ = x_1 + (x_2 + (x_3 + (... (x_{n-1}+(x_n \u22cf 0)) ...) \u22cf 0) \u22cf 0) \u22cf 0 $\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u043c \u0443\u0434\u043e\u0431\u043d\u0435\u0435 \u043f\u0435\u0440\u0435\u043d\u0443\u043c\u0435\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18a\/332\/fac\/18a332facc25acf29ed6ea5b74d88fdd.svg\" alt=\"$ (x_n + x_{n-1} + x_{n-2} + ... + x_1) \u22cf (x_n + x_{n-1} + x_{n-2} + ... + x_2) \u22cf ... \u22cf (x_n + x_{n-1}) \u22cf x_n \u22cf 0 = \\\\ = x_n + (x_{n-1} + (x_{n-2} + (... (x_2+(x_1 \u22cf 0)) ...) \u22cf 0) \u22cf 0) \u22cf 0 $\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>\u0417\u0430\u043f\u0438\u0448\u0435\u043c \u043b\u0435\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0439, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u0432\u044b\u0448\u0435. \u0412 \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u043a\u043e\u0431\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0438 \u0434\u043e \u043a\u043e\u043d\u0446\u0430. \u0412\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u043a\u043e\u0431\u043e\u043a \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 <code>tails<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0441\u043a\u043e\u0431\u043a\u0430\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0427\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 <code>map<\/code> \u0441 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c <code>sum<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">map sum . tails<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418 \u0432\u0441\u0435 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0435 \u0441\u043a\u043e\u0431\u043a\u0438 \u0437\u0430\u0442\u0435\u043c \u0441\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>max<\/code>. \u0422.\u0435. \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>max<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">max . map sum . tails<\/code><\/pre>\n<p>  <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0430\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0441\u0445\u0435\u043c\u044b \u0413\u043e\u0440\u043d\u0435\u0440\u0430. \u0417\u0434\u0435\u0441\u044c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e \u0438 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0432\u043c\u0435\u0448\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u044b \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u2014 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 <code>max<\/code>. \u0422\u0430\u043a\u0438\u043c \u0436\u0435 \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 <code>foldl<\/code> (<code>foldLeft<\/code>). \u041d\u0430\u043c \u043d\u0430\u0434\u043e \u043b\u0438\u0448\u044c \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 (<strong>UPD<\/strong>: \u0441\u043f\u0430\u0441\u0438\u0431\u043e <a href=\"https:\/\/habr.com\/ru\/users\/corwinh\/\" class=\"user_link\">CorwinH<\/a>, \u043e\u0431\u0440\u0430\u0442\u0438\u0432\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440 \u0438\u0434\u0451\u0442 \u043f\u0435\u0440\u0432\u044b\u043c \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u043c):<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">(accumulator, element) => element + accumulator \u22cf 0<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0442\u0430\u043a\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <code>\u2299<\/code> (\u0438\u043b\u0438 <code>summax0<\/code>). \u0422\u043e\u0433\u0434\u0430 <\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">val summax0 =   (accumulator: Int, element: Int) => element + math.max(accumulator, 0)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">\u2299 accumulator element = element + (max 0 accumulator) \u2299 = (+) . (max 0)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u0430\u0447\u0430\u043b\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0441 \u043d\u0435\u0439\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>max<\/code>. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435\u0439\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432\u043e\u0437\u044c\u043c\u0451\u043c <code>-\u221e<\/code> (\u0438\u043b\u0438 <code>Int.MinValue<\/code>). \u041f\u0440\u0430\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0441\u0445\u0435\u043c\u044b \u0413\u043e\u0440\u043d\u0435\u0440\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0438\u0434:<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">foldLeft(Int.MinValue)(summax0)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">foldl(\u2299)(-\u221e)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418 \u0432 \u0446\u0435\u043b\u043e\u043c \u0441\u0445\u0435\u043c\u0430 \u0413\u043e\u0440\u043d\u0435\u0440\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">max . map sum . tails \u2261 foldl(\u2299)(-\u221e)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0441\u0445\u0435\u043c\u043e\u0439, \u0447\u0442\u043e\u0431\u044b \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0434\u043b\u044f <code>mss<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map (max . (map sum) . tails) . inits mss = max . map (foldl(\u2299)(-\u221e)           ) . inits<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(    max `compose` map(sum) `compose` tails      ) `compose` inits val mss: Array[Int] => Int =      max `compose` map(    foldLeft(Int.MinValue)(summax0)             ) `compose` inits<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"skanirovanie-s-nakopleniem\">\u0421\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0441 \u043d\u0430\u043a\u043e\u043f\u043b\u0435\u043d\u0438\u0435\u043c<\/h2>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u0438 <code>foldl<\/code> \u0438 <code>foldr<\/code> \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u044e\u0442 \u043f\u043e\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043d\u0443\u044e \u0441\u0432\u0451\u0440\u0442\u043a\u0443 \u0441 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u043e\u043c \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0442 \u0441\u0430\u043c\u043e\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0418\u043d\u043e\u0433\u0434\u0430 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0432\u0441\u0435 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c\u044b\u0435 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0441\u0432\u0451\u0440\u0442\u043a\u0438, \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430. \u0422\u0430\u043a\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0442\u0430\u043a\u0436\u0435 \u0438\u043c\u0435\u044e\u0442\u0441\u044f \u0432 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0435 \u0438 \u043d\u043e\u0441\u044f\u0442 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f <code>scanl<\/code> \u0438 <code>scanr<\/code> (<code>scanLeft<\/code>, <code>scanRight<\/code>):<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">scanl :: (b -> a -> b) -> b -> [a] -> [b]<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0431\u044b\u0447\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <code>foldl<\/code> \u043b\u0435\u0433\u043a\u043e \u0432\u044b\u0440\u0430\u0436\u0430\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 <code>scanl<\/code>. \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442: <\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">foldl f zero \u2261 last . scanl f zero<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0438 <code>scanl<\/code> \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u0447\u0435\u0440\u0435\u0437 <code>foldl<\/code>. \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0437\u0432\u0430\u0442\u044c <code>foldl<\/code> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043d\u0430\u0447\u0430\u043b \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">scanl f zero \u2261 map (foldl f zero) . inits<\/code><\/pre>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u0434\u0432\u0430 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e. \u0412 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(n^2)<\/code>, \u0430 \u0432 \u043b\u0435\u0432\u043e\u0439 \u2014 <code>O(n)<\/code>. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044d\u0442\u043e \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u0438\u043c\u0435\u0435\u0442 \u0441\u043c\u044b\u0441\u043b \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0434\u043b\u044f \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438. \u0412 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>f<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <code>summax0<\/code> (<code>\u2299<\/code>), \u0430 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f <code>Int.MinValue<\/code> (<code>-\u221e<\/code>), \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0442\u0430\u043a\u043e\u0435 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">map (foldl \u2299 -\u221e) . inits \u2261 scanl \u2299 -\u221e<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">map(foldLeft(Int.MinValue)(summax0)) `compose` inits \u2261 scanLeft(Int.MinValue)(summax0)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044f \u0432 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0434\u043b\u044f <code>mss<\/code>, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map (foldl(\u2299)(-\u221e)) . inits mss = max . scanl \u2299 -\u221e<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` map(foldLeft(Int.MinValue)(summax0)) `compose` inits val mss: Array[Int] => Int =      max `compose` scanLeft(Int.MinValue)(summax0)<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"svyortka-skanirovaniya\">\u0421\u0432\u0451\u0440\u0442\u043a\u0430 \u0441\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0412 \u043d\u0430\u0448\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u043c\u044b \u0434\u0432\u0430\u0436\u0434\u044b \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043f\u043e \u0441\u043f\u0438\u0441\u043a\u0443 \u0434\u043b\u0438\u043d\u043e\u0439 <code>n<\/code> \u0438 \u043f\u043e \u0434\u043e\u0440\u043e\u0433\u0435 \u0432\u044b\u043d\u0443\u0436\u0434\u0435\u043d\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 <code>O(n)<\/code>. \u041c\u043e\u0436\u0435\u043c \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u044d\u0442\u0438 \u0434\u0432\u0430 \u043f\u0440\u043e\u0445\u043e\u0434\u0430 \u0438 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445 \u0432 \u0434\u0432\u0443\u0445 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u044f\u0447\u0435\u0439\u043a\u0430\u0445. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0430\u0440\u0443.<\/p>\n<p>  <\/p>\n<p>\u0417\u0430\u043f\u0438\u0448\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>max<\/code> \u0447\u0435\u0440\u0435\u0437 <code>foldl<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">max \u2261 foldl \u22cf -\u221e<\/code><\/pre>\n<p>  <\/p>\n<p>\u0410\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440 \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0435 \u043f\u0430\u0440\u044b.<\/p>\n<p>  <\/p>\n<p><code>scanl<\/code> \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0441\u0432\u043e\u0435\u0433\u043e \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u0430 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430. \u0422.\u043a. \u043c\u044b \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434, \u0442\u043e \u043d\u0430\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a, \u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u0448\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u0430 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435. \u042d\u0442\u043e\u0442 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0435 \u043f\u0430\u0440\u044b.<br \/>  \u0421\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u0443\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>maxsummax0<\/code>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u043f\u0430\u0440\u0443 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u043e\u0432 \u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 (<strong>UPD<\/strong> \u043f\u043e \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u044e <a href=\"https:\/\/habr.com\/ru\/users\/corwinh\/\" class=\"user_link\">CorwinH<\/a>):<\/p>\n<p>  <\/p>\n<pre><code class=\"scala\">def maxsummax0(pairOfAccumulators: (Int, Int), element: Int): (Int, Int) =   val (w1, v1) = pairOfAccumulators   val v2 = summax0(v1, element)   val w2 = math.max(w1, v2)   (w2, v2)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">maxsummax0 (w1, v1) element = (w2, v2)   where     v2 = summax0 v1 element     w2 = max w1 v2<\/code><\/pre>\n<p>  <\/p>\n<p>\u0414\u043b\u044f <code>foldl<\/code> \u0442\u0430\u043a\u0436\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0430\u043a\u043a\u0443\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u043e\u0432. \u0422.\u043a. \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <code>scanl<\/code> \u0440\u0430\u0432\u043d\u043e <code>0<\/code> \u0438 \u043c\u044b \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043a \u043d\u0435\u043c\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <code>max<\/code> (<code>\u22cf<\/code>), \u0442\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u0434\u043b\u044f <code>foldl<\/code> \u0431\u0443\u0434\u0435\u0442 \u043f\u0430\u0440\u0430 \u043d\u0443\u043b\u0435\u0439 <code>(0, 0)<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0412 \u043a\u043e\u043d\u0446\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0422.\u0435. \u043f\u0435\u0440\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u0430\u0440\u044b <code>fst<\/code> (<code>_._1<\/code>).<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">max . scanl \u2299 -\u221e \u2261 fst . foldl maxsummax0 (0,0)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">def fst[A, B](p: (A, B)): A = p._1  fst . foldLeft((0,0))(maxsummax0)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u044d\u0442\u043e \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u0432 <code>mss<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . scanl \u2299 -\u221e mss = fst . foldl maxsummax0 (0,0)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"scala\">val mss: Array[Int] => Int =      max `compose` scanLeft(Int.MinValue)(summax0) val mss: Array[Int] => Int =      fst . foldLeft((0,0))(maxsummax0)<\/code><\/pre>\n<p>  <\/p>\n<h1 id=\"zaklyuchenie\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h1>\n<p>  <\/p>\n<p>\u041d\u0430\u0447\u0430\u0432 \u0441 \u0431\u0443\u043a\u0432\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u0438\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0443 \u043e\u043a\u0430\u0437\u0430\u043b\u0430\u0441\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u0438\u043c\u0435\u044e\u0449\u0438\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <code>O(n^3)<\/code>, \u0411\u0451\u0440\u0434 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u044f\u0434\u0430 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u043f\u043e\u043b\u0443\u0447\u0438\u043b \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c (<code>O(n)<\/code>):<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">mss = max . map sum . segs \u2261 mss = fst . foldl maxsummax0 (0,0)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0438\u0439\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/539166\/\">\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u041a\u0430\u0434\u0430\u043d\u0435<\/a>. \u0412\u044b\u0432\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0437\u0430\u043e\u0434\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e\u043c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u043f\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/758810\/\"> https:\/\/habr.com\/ru\/articles\/758810\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0438\u0437 \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445, \u043f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u043c\u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0411\u0451\u0440\u0434 \u0438 \u041c\u0435\u0435\u0440\u0442\u0435\u043d\u0441 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 <a href=\"https:\/\/academic.oup.com\/comjnl\/article\/32\/2\/122\/543545?login=false\" rel=\"nofollow noopener noreferrer\">\u0444\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u043c<\/a>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0432\u044b\u0441\u0448\u0435\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <code>map<\/code>, <code>fold<\/code>, <code>scan<\/code>, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b\u0435. (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Bird%E2%80%93Meertens_formalism\" rel=\"nofollow noopener noreferrer\">\u0421\u043c. \u0442\u0430\u043a\u0436\u0435 \u043d\u0430 \u0412\u0438\u043a\u0438<\/a>). \u041d\u0438\u0436\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0432\u043e\u043b\u044c\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u0441\u0442\u0430\u0442\u044c\u0438 \u0411\u0451\u0440\u0434\u0430.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Maximum_subarray_problem\" rel=\"nofollow noopener noreferrer\">\u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0443\u043c\u043c\u044b \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430<\/a>. \u042d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u043e\u0447\u043d\u043e\u0433\u043e \u043e\u0442\u0432\u0435\u0442\u0430:<\/p>\n<p>  <\/p>\n<blockquote><p>\u0414\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0447\u0438\u0441\u0435\u043b, \u0430 \u0437\u0430\u0442\u0435\u043c \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0442\u0430\u043a\u0438\u0445 \u0441\u0443\u043c\u043c \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e.<\/p><\/blockquote>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-353966","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/353966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=353966"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/353966\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=353966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=353966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=353966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}