Share my O(n) solution in Java


  • 0
    R
    1. Calculate max sum to current element(inclusive). If last currMax < 0, there is no need to add last currMax into our current currMax, currentcurrMaxwill be the current element, whether it is positive or not. (Wish my language is not so confusing...)
    2. At the same time, renew our result by comparing current currMax and result
        public int maxSubArray(int[] nums) {
        	if(nums.length == 0) return Integer.MIN_VALUE;
        	
            int result = nums[0], maxCurr = nums[0];
            for(int i = 1; i < nums.length; i++) {
                maxCurr = maxCurr > 0 ? maxCurr + nums[i] : nums[i];
                result = Math.max(result, maxCurr);
            }
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.