{"id":194,"date":"2021-02-07T22:17:57","date_gmt":"2021-02-07T22:17:57","guid":{"rendered":"https:\/\/gnikesh.com\/?p=194"},"modified":"2021-03-05T19:29:08","modified_gmt":"2021-03-05T19:29:08","slug":"maximum-subsequence-sum-of-an-array","status":"publish","type":"post","link":"https:\/\/gnikesh.com\/index.php\/2021\/02\/07\/maximum-subsequence-sum-of-an-array\/","title":{"rendered":"Maximum Subsequence Sum of an Array"},"content":{"rendered":"\n

First, let’s define what a maximum subsequence sum problem is. Suppose we have an array [5, -3, 4, -7, 8, 7, 4, -1] then we would want to find a contiguous sequence that has the maximum sum. In this case, subsequence [8, 7, 4] has the maximum sum i.e. 19. It’s worth noting that if the array did not have any negative numbers, the subsequence with maximum sum would be simply the given array. And, for this problem, let’s consider if all elements are negative, the maximum sum would be 0. <\/p>\n\n\n\n\n\n\n\n

Mathematically, if A is an array with ‘n’<\/em> elements, we could define the maximum subsequence sum of A as<\/p>\n\n\n\n

<\/p>\n\n\n\n

(1) <\/span>   <\/span>\"\begin{equation*}\max\{\sum_{k=i}^{j-1}A\left[k\right]|\:0\le i\le j\le n\}\end{equation*}\"<\/p><\/p>\n\n\n\n

Let’s solve this problem in few ways<\/p>\n\n\n\n

1. A simple brute force approach to generate all subsequence sums and return the highest sum. <\/strong>Let’s see a code to implement definition (1) in python<\/p>\n\n\n\n

\n
def max_subsequence_sum(A):\n    max_sum = 0\n    n = len(A)\n    for i in range(n):\n        for j in range(n):\n            curr_sum = 0\n            for k in range(i, j):\n                curr_sum += A[k]\n            max_sum = max(max_sum, curr_sum)\n    return max_sum\n   <\/code><\/pre>\n<\/div><\/div>\n\n\n\n
When we run this function with [5, -3, 4, -7, 8, 7, 4, -1], it returns 19 which is a correct answer. If we look into the code, this function has 3 nested loops, and if the size of the array becomes very large, this function takes really long time to get the results. For this function, we have:<\/p>\n\n\n\n
\"Time\ Complexity: O(n^3)\"
\"Space\ Complexity: O(1)\"<\/span><\/p>\n\n\n\n
So we definitely need to improve the time complexity of this function.<\/p>\n\n\n\n
2. Removing unnecessary loops from our previous solution.<\/strong> Let’s see how we can optimize the above function by removing the second for<\/em> loop. Python code would look something like<\/p>\n\n\n\n
def max_subsequence_sum(A):\n    max_sum = 0\n    n = len(A)\n    for i in range(n):\n            curr_sum = 0\n            for k in range(i, n):\n                curr_sum += A[k]\n                max_sum = max(max_sum, curr_sum)\n    return max_sum<\/code><\/pre>\n\n\n\n
For this function, we would then have:<\/p>\n\n\n\n
\"Time\ Complexity: O(n^2)\"
\"Space\ Complexity: O(1)\"<\/span><\/p>\n\n\n\n
Can we do better? Let’s look at a top-down approach.<\/p>\n\n\n\n
3. A Top-Down<\/strong> Solution. For a given array A with n number of elements i.e. A[0…n-1], we can represent the maximum subsequence sum of A as sn<\/sub>. And sn-1<\/sub> would then be A[0…n-2] for n > 0. Then our overall maximum subsequence sum would be the maximum of sn-1<\/sub> and all of the sums of subsequences A[i…n-1] for 0 <= i <= n which we represent as tn<\/sub>.<\/p>\n\n\n\n
   <\/span>   <\/span>\"\[ s_n = \left\{ \begin{array}{cc} 0 & if \quad n = 0 \\ max(s_{n-1}, t_n) & if \quad n > 0 \end{array} \right. \]\"<\/p><\/p>\n\n\n\n
And, this sum of \"t_n\", which we call maximum suffix sum will be defined as <\/p>\n\n\n\n
 (2) <\/span>   <\/span>\"\begin{equation*}\max\{\sum_{k=i}^{n-1}A\left[k\right]|\:0\le i\le j\le n\}\end{equation*}\"<\/p><\/p>\n\n\n\n
And we can calculate \"t_n\" as<\/p>\n\n\n\n
   <\/span>   <\/span>\"\[ t_n = max(0, A[n-1] + t_{n-1} )\]\"<\/p><\/p>\n\n\n\n
So, implementing the given specification as a python code, we would get<\/p>\n\n\n\n
def max_subsequence_sum(A):\n\tn = len(A)\n\tif n == 0:\n\t\treturn 0\n\telse:\n\t\treturn max(max_subsequence_sum(A[:n-1]), max_suffix_sum(A[:n]))\n\ndef max_suffix_sum(A):\n\tn = len(A)\n\tif n == 0:\n\t\treturn 0\n\telse:\n\t\treturn max(0, A[n-1] + max_suffix_sum(A[:n-1]))\n<\/code><\/pre>\n\n\n\n
Running max_subsequence_sum<\/em> with [5, -3, 4, -7, 8, 7, 4, -1] indeed gives us 19. However, analyzing the code, this top-down approach still runs in \"n^2\" time. Even worse, it uses a stack and this stack space grows linearly with n–size of the input. So, for this approach we have,<\/p>\n\n\n\n
\"Time\ Complexity:  O(n^2)\"
\"Space\ Complexity:  O(n)\"<\/p>\n\n\n\n
Although this approach did not give us an advantage over the previous method, we have techniques to improve the stack usage. However, we can implement this in a bottom-up fashion and remove using recursion altogether. Let’s see how we might do it.<\/p>\n\n\n\n
4. Bottom-up approach to calculate maximum subsequence sum<\/strong>. We can optimize the above implementation such that we can compute \"s_i\" immediately after computing \"t_i\". Let’s look at the code how we can implement it. <\/p>\n\n\n\n
def max_subsequence_sum(A):\n\tmax_sum = 0\n\tmax_suf_sum = 0\n\tfor i in range(len(A)):\n\t\tmax_suf_sum = max(0, max_suf_sum + A[i])\n\t\tmax_sum = max(max_sum, max_suf_sum)\n\treturn max_sum<\/code><\/pre>\n\n\n\n
So, we can see that we have optimized our solution a lot and analyzing this implementation, we find that it runs in linear time \"n\" with constant space usage. So, for this implementation, we have<\/p>\n\n\n\n
\"Time\ Complexity: O(n)\"
\"Space\ Complexity: O(1)\"<\/p>\n\n\n\n
What if we also want to return the subsequence as well? This should not be too difficult once we understand the above implementation. Let’s use i_index<\/em> and j_index<\/em> as two variables to keep track of our desired subsequence. Then finally we return subsequence with these two indexes as starting and ending index for the maximum subsequence. Let us see in the code how we can implement it.<\/p>\n\n\n\n
 <\/p>\n\n\n\n
def max_subsequence_sum(A):\n\tmax_sum = 0\n\tmax_suf_sum = 0\n\ti_index, j_index = 0, 0\n\ttemp_idx = 0\n\n\tfor i in range(len(A)):\n\t\tmax_suf_sum += A[i]\n\t\tif max_suf_sum > max_sum:\n\t\t\tmax_sum = max_suf_sum\n\t\t\tj_index = i\n\t\t\ti_index = temp_idx\n\n\t\tif max_suf_sum < 0:\n\t\t\ttemp_idx = i + 1\n\t\t\tmax_suf_sum = 0\n\n\treturn A[i_index:j_index+1], max_sum<\/code><\/pre>\n\n\n\n
This implementation still runs in \"O(n)\" with constant space used. Thank you for making it till the end. Yaay!<\/p>\n","protected":false},"excerpt":{"rendered":"
First, let’s define what a maximum subsequence sum problem is. Suppose we have an array [5, -3, 4, -7, 8, 7, 4, -1] then we would want to find a contiguous sequence that has the maximum sum. In this case, subsequence [8, 7, 4] has the maximum sum i.e. 19. It’s worth noting that if […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[13,7],"tags":[21,19],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-algorithms-data-structures","category-computer-science","tag-algorithm","tag-computer"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":75,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":280,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions\/280"}],"wp:attachment":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}