mmte-002-solved-assignment-2024-ss-8e24e610-06c9-4b43-84f6-a5bf6ef5ab5c

1. a) The maximum subsequence sum problem is defined as follows: If $a_1,a_2,\dots ,a_n$$a_1,a_2,\dots ,a_n$a_(1),a_(2),dots,a_(n)a_1, a_2, \ldots, a_n$a_1,a_2,\dots ,a_n$ are in $\mathbf{Z}$$\mathbf{Z}$Z\mathbf{Z}$\mathbf{Z}$, find the maximum value $\sum _{k=i}^j{a}_i$$\sum _{k=i}^j a_i$sum_(k=i)^(j)a_(i)\sum_{k=i}^j a_i$\sum _{k=i}^j{a}_i$, for all $\mathrm{i},\mathrm{j},1\le i\le j\le n$$\mathrm{i},\mathrm{j},1\le i\le j\le n$i,j,1 <= i <= j <= n\mathrm{i}, \mathrm{j}, 1 \leq i \leq j \leq n$\mathrm{i},\mathrm{j},1\le i\le j\le n$. We assume that the answer is 0 if all the $a_i$$a_i$a_(i)a_i$a_i$ are negative or if the sum is empty. The following algorithm finds a solution to the problem. Here, we assume that $a_i\mathrm{s}$$a_i\mathrm{s}$a_(i)sa_i \mathrm{~s}$a_i\mathrm{s}$ are stored in the array $\mathrm{A}$$\mathrm{A}$A\mathrm{A}$\mathrm{A}$.

1. Initialization (Beginning of the loop, $i=1$$i=1$i=1i = 1$i=1$): Before the first iteration, MaxSum is set to 0, which is correct since we have not encountered any elements of the array and the maximum subsequence sum of an empty array is 0.
2. Maintenance (During the loop): At each iteration, we add $A[i]$$A[i]$A[i]A[i]$A[i]$ to Sum. If Sum becomes greater than MaxSum, we update MaxSum to Sum because we have found a larger subsequence sum ending at $i$$i$ii$i$. If Sum is negative, we set it to 0 since a maximum subsequence sum cannot be negative (as per the problem statement, we take the maximum sum to be 0 in this case). This maintains the loop invariant because MaxSum continues to represent the maximum sum of any subsequence that ends at or before $i$$i$ii$i$.
3. Termination (End of the loop): When the loop terminates (after the final iteration when $i=n$$i=n$i=ni = n$i=n$), the loop invariant tells us that MaxSum holds the maximum subsequence sum of the entire array $A[1..n]$$A[1..n]$A[1..n]A[1..n]$A[1..n]$, because every element has been considered, and MaxSum has been updated accordingly throughout the loop.

1. Initialization (Line 1): Initializing Sum and MaxSum takes constant time, so this part is $O(1)$$O(1)$O(1)O(1)$O(1)$.
2. For Loop (Lines 2-8):
   • The loop iterates $n$$n$nn$n$ times, where $n$$n$nn$n$ is the length of the array $A$$A$AA$A$.
   • Inside the loop, updating Sum (Line 4) and the comparison (Line 5) are constant-time operations, so they each take $O(1)$$O(1)$O(1)O(1)$O(1)$ time per iteration.
   • Updating MaxSum (Line 6) and resetting Sum (Line 8) are also constant-time operations, executed at most once per iteration, so they also take $O(1)$$O(1)$O(1)O(1)$O(1)$ time per iteration.

3. Overall Runtime: Combining the initialization and the loop, the overall runtime of the algorithm is $O(1)+O(n)=O(n)$$O(1)+O(n)=O(n)$O(1)+O(n)=O(n)O(1) + O(n) = O(n)$O(1)+O(n)=O(n)$.