1, 题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:

  1. 输入: [-2,1,-3,4,-1,2,1,-5,4],
  2. 输出: 6
  3. 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

1, 合并

  1. 循环
  2.     寻找第一个正值,记录最大值,当前值
  3.     不断把下一个值加入当前值,直到当前值<0,记录每一次变化的最大值
  4. 思考:
  5.     1,把数组连续的符号相同的值合并,最后数组是正负正负...类似这样的数组
  6.     重复下面的动作
  7.         舍弃负值,最左侧的两个正负合并,结果如果是负,舍弃,如果是正,再次合并成一个正值
  1. #scala
  2. object Solution {
  3.     def maxSubArray(nums: Array[Int]): Int = {
  4.         if (nums.isEmpty) {
  5.             return 0
  6.         }
  7.         var i = 0
  8.         var max_value = nums(0)
  9.         var current = nums(0)
  10.         while (i < nums.length) {
  11.             while (i < nums.length && nums(i) <= 0) {
  12.                 current = nums(i)
  13.                 max_value = max_value.max(current)
  14.                 i += 1
  15.             }
  16.             if (i < nums.length) {
  17.                 current = nums(i)
  18.                 max_value = max_value.max(current)
  19.                 i+=1
  20.             }
  21.             while (i < nums.length && current >= 0) {
  22.                 current += nums(i)
  23.                 max_value = max_value.max(current)
  24.                 i+=1
  25.             }
  26.         }
  27.         max_value
  28.     }
  29. }
# scala变形
object Solution {
    def maxSubArray(nums: Array[Int]): Int = {
        if (nums.isEmpty) {
            return 0
        }

        var max_value = nums(0)
        var current = nums(0)
        var i = 1
        while (i < nums.length) {
            if (current >= 0) {
                current += nums(i)
            } else {
                current = nums(i)
            }
            max_value = max_value.max(current)
            i += 1
        }
        max_value
    }
}

#python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        current = nums[0]
        max_value = nums[0]
        i = 1
        while i < len(nums):
            if current >= 0:
                current += nums[i]
            else:
                current = nums[i]
            max_value = max(max_value, current)
            i += 1
        return max_value

2, 动态规划

f(n)定义为:以第n个元素为尾元素的最大子序列
    这么定义有一个最大的好处,可以轻松推导出状态转移方程
    f(n)=max(f(n-1)+an,an)
    而连续子数组最大值必定是某一个f(n)
    https://en.wikipedia.org/wiki/Maximum_subarray_problem

#scala
object Solution {
    def maxSubArray(nums: Array[Int]): Int = {
        if (nums.isEmpty) {
            return 0
        }

        var max_value = nums(0)
        var fn = nums(0)

        for (i <- Range(1, nums.length)) {
            fn = scala.math.max(nums(i), fn + nums(i))
            max_value = max_value.max(fn)
        }

        max_value
    }
}

#python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        max_value = nums[0]
        fn = nums[0]
        for i in range(1, len(nums)):
            fn = max(nums[i], fn + nums[i])
            max_value = max(max_value, fn)
        return max_value

**