{"id":3416,"date":"2017-12-17T13:45:09","date_gmt":"2017-12-17T08:15:09","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=3416"},"modified":"2017-12-17T13:45:09","modified_gmt":"2017-12-17T08:15:09","slug":"maximum-sum-contiguous-sub-array","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2017\/12\/17\/maximum-sum-contiguous-sub-array\/","title":{"rendered":"Maximum sum contiguous sub-array"},"content":{"rendered":"<p><strong>Problem statement<\/strong> &#8211; Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array <em>A[0, 1, 2 &#8230; N]<\/em>, we need to find a sub-array <em>A[i, i + 1, i + 2, &#8230; j]<\/em> such that the sum of elements in the sub-array is maximum.<\/p>\n<p><strong>Clues<\/strong> &#8211;<\/p>\n<ul>\n<li>Your solution should be O(N) in time and O(1) in space.<\/li>\n<li>Can you think of a solution which solves the problem in a single scan of the array?<\/li>\n<\/ul>\n<p><strong>Solution<\/strong> &#8211; This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane&#8217;s Algorithm. In this algorithm, we keep adding elements to a <em>sum<\/em> variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the <em>sum<\/em> variable becomes negative, we cast off the the sub-array seen so far and reset <em>sum<\/em> variable. The final answer will be the maximum of all the values which were stored in <em>sum<\/em> over all iterations.<\/p>\n<p>Example &#8211; For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]\n<div class=\"su-table su-table-alternate\">\n<table style=\"height: 628px\" width=\"729\">\n<tbody>\n<tr>\n<td>A[i]<\/td>\n<td>Sub-array<\/td>\n<td><em>sum<\/em><\/td>\n<td>Max sub-array<\/td>\n<td><em>maxSum<\/em><\/td>\n<\/tr>\n<tr>\n<td>-2<\/td>\n<td>[-2]<\/td>\n<td>0<\/td>\n<td>[-2]<\/td>\n<td>-2<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>[1]<\/td>\n<td>1<\/td>\n<td>[1]<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>-3<\/td>\n<td>[-3]<\/td>\n<td>0<\/td>\n<td>[1]<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>[4]<\/td>\n<td>4<\/td>\n<td>[4]<\/td>\n<td>4<\/td>\n<\/tr>\n<tr>\n<td>-1<\/td>\n<td>[4, -1]<\/td>\n<td>3<\/td>\n<td>[4]<\/td>\n<td>4<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>[4, -1, 2]<\/td>\n<td>5<\/td>\n<td>[4, -1, 2]<\/td>\n<td>5<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>[4, -1, 2, 1]<\/td>\n<td>6<\/td>\n<td>[4, -1, 2, 1]<\/td>\n<td>6<\/td>\n<\/tr>\n<tr>\n<td>-5<\/td>\n<td>[-5]<\/td>\n<td>3<\/td>\n<td>[4, -1, 2, 1]<\/td>\n<td>6<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>[-5, 4]<\/td>\n<td>3<\/td>\n<td>[4, -1, 2, 1]<\/td>\n<td>6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><strong>Code<\/strong> &#8211;<\/p>\n<pre class=\"brush: java; title: ; notranslate\" title=\"\">\npublic class Solution {\n\tpublic int maxSubArray(List&lt;Integer&gt; a) {\n\t    int sum = 0;\n\t    int maxSum = Integer.MIN_VALUE;\n\t    \n\t    for (int i = 0; i &lt; a.size(); ++i) {\n\t        if (sum + a.get(i) &lt; 0) {\n\t            \/\/ Adding this element will make the current\n\t            \/\/ subarray sum negative, so don't add this element\n\t            \/\/ and start a new subarray with next element\n\t            sum = 0;\n\t        } else {\n\t            \/\/ Adding this element will increase the\n\t            \/\/ current subarray sum, so add this\n\t            \/\/ element to the current subarray\n\t            sum += a.get(i);\n\t        }\n\t        \n\t        \/\/ maxSum is the maximum of -\n\t        \/\/\n\t        \/\/ 1. maxSum so far\n\t        \/\/ 2. if sum == 0, then a.get(i) which is proably a -ve number\n\t        \/\/ 3. if sum != 0, then sum of subarray so far\n\t        maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum);\n\t    }\n\t    \n\t    return maxSum;\n\t}\n}\n<\/pre>\n<p>If you didn&#8217;t understand why we need the &#8220;<em>sum == 0 ? a.get(i) : sum<\/em>&#8221; condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you&#8217;d want to return the largest among the negative values. Now remember, <em>sum<\/em> variable doesn&#8217;t store negative values, so when it holds 0, we consider <em>A[i]<\/em> instead of <em>sum<\/em>. Give it a little thought, I&#8217;m sure you&#8217;ll understand it. If you need a more explanation, refer to my post on <a href=\"http:\/\/theoryofprogramming.azurewebsites.net\/2016\/10\/21\/dynamic-programming-kadanes-algorithm\/\">Kadane&#8217;s Algorithm<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Find a contiguous sub-array whose sum is maximum. Using the dynamic programming based Kadane&#8217;s Algorithm, we can solve this in O(N) time.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[16],"tags":[20,22,43,61],"class_list":["post-3416","post","type-post","status-publish","format-standard","hentry","category-array-interview-questions","tag-arrays","tag-arrays-interview-questions","tag-dynamic-programming","tag-interview-questions"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3416","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=3416"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3416\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=3416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/categories?post=3416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/tags?post=3416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}