LeetCode - Algorithms - 53. Maximum Subarray

Tagged as easy, I feel it is not easy to solve. dynamic programming class problem. The solution is others, I only verify it.

Java

1 Kadane’s algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
    	int max = Integer.MIN_VALUE;
    	int count = 0;
    	for(int i=0;i<nums.length;i++) {
    		count += nums[i];
    		if (count>max)
    			max = count;
    		if (count<0)
    			count = 0;
    	}
    	return max;        
    }
}

Submission Detail

  • 202 / 202 test cases passed.
  • Runtime: 10 ms
  • Your runtime beats 40.59 % of java submissions.

2 DP

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

Submission Detail

  • 202 / 202 test cases passed.
  • Runtime: 7 ms
  • Your runtime beats 89.29 % of java submissions.

ref