This Bonus Question is worth 10 points if answered correctly…
This Bonus Question is worth 10 points if answered correctly, and will be added to any final score which you earn from the base 100 points possible. If you choose not to attempt it, then it will not take any points away from the base 100 points which you can earn (i.e. it will add “0”, as listed on Canvas). Give a linear time algorithm for the maximum subarray problem. Also justify the correctness and time complexity, at least informally. Hint: Solve A using information from the solution of A. You may need more than just the optimum solution for A.