Maximum Subarray

Easy Subarray LinkedIn Enumeration Greedy Array

LintCode: http://www.lintcode.com/en/problem/maximum-subarray/

LeetCode: https://leetcode.com/problems/maximum-subarray/#/description

Question

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice
The subarray should contain at least one number.

Example
Given the array [−2,2,−3,4,−1,2,1,−5,3] , the contiguous subarray [4,−1,2,1] has the largest sum = 6 .

Challenge
Can you do it in time complexity O(n)?

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

Thinking

Same as the problem Continous Subarray Sum

Solution

Java

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
}