-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathkadanes-algorithm.html
44 lines (37 loc) · 1.37 KB
/
kadanes-algorithm.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>What is dynamic programming?</title>
<link rel="stylesheet" href="css/css.css" type="text/css" media="all">
<link rel="stylesheet" href="css/prism.css" type="text/css" media="all">
<link rel="stylesheet" href="css/latex.css" type="text/css" media="all">
</head>
<body>
<h1 id="what-is-dynamic-programming%3F">What is dynamic programming?</h1>
<blockquote>
<p>Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'</p>
</blockquote>
<h1 id="kadane's-algorithm">Kadane's algorithm</h1>
<h2 id="question%3A">Question:</h2>
<blockquote>
<p>A popular "Maximum Subarray Problem"</p>
</blockquote>
<p>You are given some array of integer values, find greatest sum by summing up some subarray.</p>
<pre><code>[1, 2, 3, -3, -9, 19, 2, 1, 0, -1, 4, -2]
</code></pre>
<p>The main complication in this problem comes with negative numbers.</p>
<h2 id="solution-in-bash-below.">Solution in bash below.</h2>
<pre><code class="language-bash">max_ending=$1
max_so_far=$1
shift
for i in ${@}
do
max_ending=$(( $i > $max_ending + $i ? $i : $max_ending + $i ))
max_so_far=$(( $max_so_far > $max_ending ? $max_so_far : $max_ending ))
done
echo $max_so_far
</code></pre>
<script src="js/prism.js"></script>
</body>
</html>