NOTE: Proof is needed such as by induction, contradiction, or example!

1. [10 pts] You are given a one dimensional array that may contain both positive and negativ integers. Give an O(n log n) algorithm to find the sum of contiguous (ie. next to one another, i sequence) subarray of numbers which has the largest sum. For example, if the given array is then the maximum subarray sum is 7 (the subarray is marked in boldface). Argue that your alg rithm is correct