1000003. Contiguous Sequence LCCI

难度: Easy

题目描述

You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the 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.

解题思路

代码实现

解决方案

java

class Solution {
    public int maxSubArray(int[] nums) {

        int max = nums[0];
        

        int curSum = nums[0];

        
        for (int right = 1; right < nums.length; right++) {
             curSum += nums[right];
             curSum = Math.max(curSum,nums[right]);
             max = Math.max(max,curSum);

        }

        return max;

    }
}