Given a length-n array of integers A[1...n], we would like to find maximum sum which could...

Transcribed Image Text:

Given a length-n array of integers A[1...n], we would like to find maximum sum which could be obtained by adding elements in a subsequence of A if we are allowed to start anywhere in A but once we start, we can either take the element after the previously selected element or the one after, i.e, gaps of length at most 1 are allowed in the subsequence. More formally, given A find the maximum S such that there is an integer 0 ≤ m ≤n and indices 1 ≤ ₁ <...< im <n such that it+1 is either it or it + 1, for t = 1,...,m - 1 A[i] + ... + A[im] = S. Note that m = 0 corresponds the empty sequence, whose sum is 0, which could the best possible if all the elements in A are negative or if A is the empty array. For instance, for A [-10,-1, 2, 200, -1000, -10, -10, -10,-10, 500, 3, -7,0], the max is 685: elements of A which achieve the max are highlighted. ● = Design an efficient algorithm to solve this problem. In addition the max sum, explain how you can find a subsequence of A which achieves the max. Aim for linear time. Don't try to read the following hint unless you are stuck (to read it you need to magnify the PDF file and properly read it in reverse order); try first to solve it on your own without help. (Hint: Activate Windows Go to Settings to activate Windows. Given a length-n array of integers A[1...n], we would like to find maximum sum which could be obtained by adding elements in a subsequence of A if we are allowed to start anywhere in A but once we start, we can either take the element after the previously selected element or the one after, i.e, gaps of length at most 1 are allowed in the subsequence. More formally, given A find the maximum S such that there is an integer 0 ≤ m ≤n and indices 1 ≤ ₁ <...< im <n such that it+1 is either it or it + 1, for t = 1,...,m - 1 A[i] + ... + A[im] = S. Note that m = 0 corresponds the empty sequence, whose sum is 0, which could the best possible if all the elements in A are negative or if A is the empty array. For instance, for A [-10,-1, 2, 200, -1000, -10, -10, -10,-10, 500, 3, -7,0], the max is 685: elements of A which achieve the max are highlighted. ● = Design an efficient algorithm to solve this problem. In addition the max sum, explain how you can find a subsequence of A which achieves the max. Aim for linear time. Don't try to read the following hint unless you are stuck (to read it you need to magnify the PDF file and properly read it in reverse order); try first to solve it on your own without help. (Hint: Activate Windows Go to Settings to activate Windows.

Answer rating: 100% (QA)

The problem describes a variation of the maximum subarray problem with the restriction that once an ... View the full answer