最大子段和

题目描述

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

输入格式

第一行有两个数字，分别是 $x$ 和 $N$，用空格隔开。 第二行有 $N$ 个数字，用空格隔开，表示数组元素。

输出格式

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

12 8
1 -2 3 10 -4 7 2 -5

6

提示

#### 数据范围与提示 $1≤x,N≤100000$ #### 样例解释1 最大子数组为[3 10 -4 7 2]，和为18，八戒押了12两银子，所以最后赢6两

来源

童程童美