Question

1. Could dynamic programming be applied to give an efficient solution to the followingproblems? Justify your answer in terms of the optimal substructure property on theoverlapping sub-problems. Even if you think the answer is yes, you do not need to givean algorithm; the question isnot"show us how to solve it using DP", it is "give anargument as to whether DP is a reasonable approach to try here."(a) List maximum.Input:ListLof numbers.Output:The maximum element in the list.

Answer 1

Step-by-step explanation:

The sub-problems in finding the maximum in a list is finding the maximum between the temporary maximum element and every other element in the list. There are n sub-problems for a list of n elements. They can be summarized as maximum=max(maximum, ai) for i = 1 to n. All the sub-problems are unique, so there is no overlap. So, dynamic programming is not a reasonable approach to use here since it will only cost space and will not help in decreasing the time complexity.