Understand the following algorithm. Simulate it mentally on the following four inputs, and state the outputs...

  

Transcribed Image Text:

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, -10]; (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 4 for i=1 to n sum = 0 for j=1 to n sum sum + A[j] if sum > max then sum max 8 9 return max 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? 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, -10]; (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 4 for i=1 to n sum = 0 for j=1 to n sum sum + A[j] if sum > max then sum max 8 9 return max 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?

Answer rating: 100% (QA)

This algorithm is designed to find the maximum subarray sum also known as the Maximum Subarray problem which is a classical problem in computer scienc... View the full answer