Maximum Subarray

最大和的子序列

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解析重点

1.子序列的和图像是类似股票图的，有波峰波谷
2.那我们需要记录最高点（max），及当前值（sum），当前值小于0的时候，我们需要重新开始计算sum

scala代码

object Solution {
  def maxSubArray(nums: Array[Int]): Int = {
    var sum = Integer.MIN_VALUE
    var max = sum
    for(num <- nums){
      sum = if (sum<0) num else sum+num//计算当前和值，当sum小于0时重新计算
      max=Math.max(max,sum)//计算全局最大值
    }
    max
  }
}