This assignment is a short assignment and it does not involve any programming. With this assignment, you will deepen your understanding on how Algorithms 1 and 4 (discussed in lecture on pp. 61 in the textbook) go about solving the "maximal subsequence sum" problem. You will be asked to communicate your understanding in your own words. Study both algorithms, consult your lecture notes and the text book as needed. You should not find it very difficult to understand how Algorithm1 solves the problem: it iterates over all possible subsequences of the input sequence and keeps track of the maximal sum at each iteration. The maximal subsequence sum is found at a cost of O(N). You need not write to elaborate on this. Algorithm4 is much more surprising and interesting. How can it be that the same problem can be solved with a single pass over the input values?! Task 1: Answer the following questions .... (1) What is the maximal contiguous subsum for a vector of only positive values? (Explain in general, not by specific example.) (2) What is the maximal contiguous subsum for a vector of only negative values? (Explain in general, not by specific example.) (3) Imagine a stage of problem solving in the context of Algorithm 4: previous iterations have determined som candidate (so far seen) maximal subsum; in the current iteration, a local sum has been accumulated and its value is negative. What is the significance of this fact for this current iteration relative to our goal (= finding the overall maximal subsum)? 1 2 3 4 ** * Cubic maximum contiguous subsequence sum algorithm. */ int maxSubSuml( const vector int> & a ) int maxSum = 0; for( int i = 0; i maxSum) maxSum = thisSum; return maxSum; 21 } Figure 2.5 Algorithm 1 2 3 4 5 * Linear-time maximum contiguous subsequence sum algorithm. */ int maxSubSum4 const vector int>& a ) 1 int maxSum = 0, thisSum = 0; for(int j = 0; j maxSum) maxSum = thisSum; else if( thisSum