Do it Your Self. Thank you very very much. Meiju.Video Autigers.org It\'s a big
ID: 3880973 • Letter: D
Question
Do it Your Self. Thank you very very much. Meiju.Video Autigers.org
It's a big question with multiple sub-questions. Sorry about that. But it is not too complicated, please do them with caution. Thanks a lot a lot....
(4. 12pts) Computational problem solving: Understanding an algorithm and its strategy by simulating it on a specific input Understand the following algorithm. Simulate it mentally on the following four inputs, and state the outputs produced (value returned) in each case: (a) A: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; (b) A: [-1,-2,-3,-4,-5,-6,-7, -8,-9,-101, ; (c) A: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], (d) A: [-1, 2,-3, 4,-5, 6, 7, -8, 9, -10] Algorithm Mystery (A:array[1. .n] of integer) sum, max: integer 1 sum=0 2 max-0 3 for i = 1 to n 4 5 sum for j = 1 to n sum = sum + A [j] if sum > max then 7 8 9 return max max = sum Output when input is array (a) above: Output when input is array (b) above: Output when input is array (c) above: Output when input is array (d) above: What does the algorithm return when the input array contains all negative integers? What does the algorithm return when the input array contains all non-negative integers?Explanation / Answer
The 2 loops inside the function computes the partial sum of subarray and returns the maximum possible positive subarray sum of the array through variable max.
The first loop i indicates the position which is first in the contiguous subarray. The second loop loops through all positions starting from i till the last element and calculate the maximum subsequent subarray sum. If the calculated sum is more than max, it sets the max to to the new sum and continue calculating the subarray sums. In the end, the maximum positive subarray sum is returned.
For example, given an array {-1, 2, 3, -4}
The possible subarrays are {}, {-1}, {2}, {3}, {-4}, {-1,2}, {-1,2,3}, {-1,2,3,-4}, {2,3}, {2,3,-4}, {3,-4}, {-4}.
Out of these, the subarray {2,3} has the maximum possible sum which is equal to 5.
Similarly, Let the array be A = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2]
In this case, the maximum subarray sum is 30 which we get when we add elements from 15 till 10.
15 -3 + 8 - 9 + 1 + 8 + 10 = 30. If we add any more elements at either side of this subarray, the sum will be less than 30 since the elements in both the sides are negative.
This is what this mystery function does. It calculates the maximum non negative sum found in any contiguous subarray of given array A by calculating sums of all possible subarrays and returning the maximum value of it. If all the elements of array are negative, the function will returh zero. Now, after knowing this fact, we can answer the given questions.
Output when array (a) is given as input:
Since all the elements are positive, we will get the maximum sum when we add all the elements of the array.
hence the value returned will be sum of all the values of array which is equal to
1+2+3+4+5+6+7+8+9+10 = 55.
Output when array (b) is given as input:
Since all the elements are negative and max is set to 0, we will get the maximum non negative sum when we don't add any of the elements of the array. Hence the value returned will be 0.
Output when array (c) is given as input.:
Since all elements are 0, it doesn't matter how many contiguous elements we add, the sum will always be 0, and hence the function will return 0.
Output when array (d) is given as input:
Notice that some values are negative, some values are negative. To get the maximum sum, we have to choose a subarray such that we get the maximum sum while avoiding as many negative values as possible.
Observe that the sum of first 5 values is negative. Hence we can altogether ignore them from out subarray. We start from 6th element. We will add 6, sum becomes 6. Next element is 7, we add 7, sum becomes 13. Now next element is -8 and 9 after that. If we want to add 9, we will have to add -8 too. Overall we will get +1 to our sum since 9 is greater than 8. Last element is -10 which will decrease the sum. So we will not add it.
hence our sum is 6 + 7 + -8 +9 = 14.
The function will return 14.
When function contain all the negative integers, then the function will return 0 since adding any element to 0 will make it less than 0 so we will not add anything and max sum will be 0.
When function contain all the non - negative integers, the function will return sum of all the elements in the array since that will give us the maximum sum.
Please give this solution a thumbs up and comment if you have any doubts in it.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.