Maximum Subarray Difference(LintCode 45):

Problem