Maximum Subarray Problem (16 points) Maximum Subarray Problem means to find the subarray indexed from i to j which maximize the sum of Ai ~Aj . You should notice that there may be negative ones but not all in the input array A[1..n]. (1) Give an algorithm to calculate the maximum subarray in O(n2 ) time, using Brute-Force or Divide and Conquer strategy as you like. (2) How to solve the problem in O(n) time using Dynamic Programming strategy? Give and describe the recursive equation used in the optimal substructure of the DP algorithm. (3) Given the following input array as following, used the algorithm in step (2) to calculate the maximum subarray. 8 -5 -4 10 -1 7 -3 12 -20 18

1. Brute-Force or Divide and Conquer strategy:
Brute-Force: 对于每一个子数组，计算其和，然后比较得出最大子数组。时间复杂度为O(n^2)。
Divide and Conquer: 将数组分成左右两部分，最大子数组要么在左边，要么在右边，要么跨越中间。时间复杂度为O(nlogn)。

2. Dynamic Programming strategy:
定义一个数组dp，dp[i]表示以A[i]结尾的最大子数组和。则有递推公式：dp[i] = max(dp[i-1]+A[i], A[i])。即当前最大子数组和为前一个最大子数组和加上当前元素的值，或者只包含当前元素。最终的最大子数组和为max(dp)。这个算法的时间复杂度是O(n)。

3. 使用动态规划算法，对于输入数组[8, -5, -4, 10, -1, 7, -3, 12, -20, 18]，依次计算dp数组的值：

dp[0] = 8
dp[1] = max(-5, 8-5) = 3
dp[2] = max(-4, 3-4) = 3
dp[3] = max(10, 3+10) = 13
dp[4] = max(-1, 13-1) = 12
dp[5] = max(7, 12+7) = 19
dp[6] = max(-3, 19-3) = 16
dp[7] = max(12, 16+12) = 28
dp[8] = max(-20, 28-20) = 8
dp[9] = max(18, 8+18) = 26

最终的最大子数组和为26，对应的子数组为[10, -1, 7, -3, 12, -20, 18]。