053.Maximum Subarray

Posted on | In

Solution 1: accepted 10%

Time: O(n)
Still get very bad performance (10%), try to replace syntax.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxSubArray(int[] nums) {
    int len = nums.length;
    if (len < 1) return 0;
    int sum = nums[0];
    int[] copy = new int[len];
    System.arraycopy(nums, 0, copy, 0, len);
    for(int i = 1; i < len; i++) {
        copy[i] = nums[i] > copy[i-1] + nums[i] ? nums[i] : copy[i-1] + nums[i];
        sum = sum > copy[i]? sum : copy[i];
        // Make it a little bit faster to 18ms (16%)
        // nums[i] = Math.max(nums[i], nums[i-1] + nums[i]); 
        // sum = Math.max(sum, nums[i]);
    }
    return sum;
}

Alternative: without copy (slower)

1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
    if (nums.length < 1) return 0;
    int sum = nums[0];
    for(int i = 1; i < nums.length; i++) {
        nums[i] = Math.max(nums[i], nums[i-1] + nums[i]);
        sum = Math.max(sum, nums[i]);
    }
    return sum;
}

Solution 2: accepted 17ms 25%

I think the performance varies on server condition…

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    if (nums.length < 1) return 0;
    int sum = 0;
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(max, sum); 
        if (sum < 0) 
            sum = 0; // restore negative number
    }
    return max;
}