Given A$[]=[3,4,5,2],$ let x be $6.$ Run the subset sum algorithm on A$[]$ to find out if there exists a subset of A$[]$ with sum $=$ x$.$ Show the dynamic programming matrix Sum$[$i$][$j$]$ that is needed to efficiently compute true or false for all possible i and j$.$

The matrix Sum$[][]$:

row $0$: $[$T$,$ F$,$ F$,$ F$,$ F$,$ F$,$ F$]$

row $1$: $[$

$]$

row $2$: $[$

$]$

row $3$: $[$

$]$

row $4$: $[$

$]$

What result does the subset sum algorithm return when x $=6?$ T or F$?$

Question $2(4$ points$)$

Question $2$ options:

Given the input array A$[]=[2,3,-8,-1,2,4,-2,3],$

Show the dynamic programming table Local$\_$maximum$($i$)$ for all possible i$.$

Local$\_$maximum$[]=[$

$]$

And the final answer is

$--------------$

Consider the following problem.

Input: A list of numbers, $[$A$[0],$ A$[1],$ A$[2],...,$ A$[$n$-1]].$

Output: The contiguous subsequence of maximum sum $($a subsequence of length zero has sum zero$).$

A contiguous subsequence of a list A is a subsequence made up of consecutive elements of A$.$ For instance, if A is $[5,15,30,10,5,40,10],$ then $[15,30,10]$ is a contiguous subsequence but $[5,15,40]$ is not. For the preceding example, the answer would be $[10,5,40,10],$ with a sum of $55.$

A dynamic programming solution is given below.

We focus on the $($i$+1)\_$th element A$[$i$].$

Consider every possible contiguous subsequence ending with the element A$[$i$].$

You'll notice that these sequences can be divided into two categories, the subsequence ending with $($A$[$i$-1],$ A$[$i$]),$ and the subsequence that contains a single element A$[$i$].$

We will call the maximum sum of contiguous subsequence ending exactly at A$[$i$]$ Local$\_$maximum$($i$).$

Let's say somehow I know Local$\_$maximum$($i$-1).$ Then we see that to calculate Local$\_$maximum$($i$),$ we don't need to compute the sum of all contiguous subsequence ending at A$[$i$]$ since we already know the result from contiguous subsequences ending at A$[$i$-1].$ And this leads us to the principle on which dynamic programming algorithm works.

Local$\_$maximum$($i$)=$ max$($A$[$i$],$ A$[$i$]+$Local$\_$maximum$($i$-1))$

This way, at every index i$,$ the problem is finding the maximum of just two numbers, A$[$i$]$ and $($A$[$i$]+$ Local$\_$maximum$($i$-1)).$ Everytime we solve a subproblem Local$\_$maximum$($i$),$ save the result, late we can re$-$use the result to solve the next subproblem Local$\_$maximum$($i$+1).$ Note that Local$\_$maximum$(0)$ would be A$[0]$ itself.

Thus we can create a table, or say, an array to save all the intermediate results Local$\_$maximum$($i$)$ and re$-$use the results later. The final result is the maximum of Local$\_$maximum$($i$)$ over all possible i$.$