Question

maximum sum contiguous subsequence. given a list of (possibly negative) integers, give a dynamic programming algorithm to find the contiguous subsequence of maximum sum. assume the empty subsequence has a sum of zero

Answer 1

The Maximum Subarray Problem can be solved using dynamic programming by creating an auxiliary array to keep track of the maximum subarray sum ending at each index, and then finding the maximum value in this array.

Step-by-step explanation:

The problem described is known as the Maximum Subarray Problem, which is solved using dynamic programming. The goal is to find the maximum sum contiguous subsequence in an array of integers.


The dynamic programming solution involves creating an auxiliary array, where each element at index i represents the maximum subarray sum ending at index i in the input array. The solution follows these steps:

1. Initialize an array max_sum of the same length as the input array, with its first value set to the first element of the input array or 0, whichever is higher.
   
   
2. Iterate through the input array starting from the second element. At each index i, set max_sum[i] equal to the maximum of input[i] and max_sum[i-1] + input[i]. This represents the maximum subarray sum ending at i either by starting fresh from input[i] or by extending the previous subarray.
   
   
3. The maximum value in the max_sum array is the maximum sum of the contiguous subsequence.

Here is a simple example:

• Input: [-2, -3, 4, -1, -2, 1, 5, -3]
  
  
• max_sum: [0, 0, 4, 3, 1, 2, 7, 4]
  
  
• The maximum sum contiguous subsequence is 7, from the subarray [4, -1, -2, 1, 5].