2233: 最大子段和

题目描述

八戒押x两银子，猫掌柜给定一个乱序数组arr，长度为N，有正数也有负数，正数表示赢钱，负数表示输钱。求arr的一个连续子数组，使得子数组的和最大，这样八戒才能尽可能的赢钱。这个和最大的子数组叫做最大子段和。

输入描述

第一行有两个数字，分别是x和N，用空格隔开，1<=x,N<=100000，第二行有N个数字，用空格隔开，表示数组元素

输出描述

输出八戒最多赢多少钱，若八戒想即时止损，则输出一个负数，表示八戒最少输多少钱。

提示

【样例解释1】
最大子数组为[3 10 -4 7 2]，和为18，八戒押了12两银子，所以最后赢6两