O(n) Easy Solution with Explanation


  • 0
    D

    Introduction
    For this problem, the end result that we need is the maximum possible sum of a sub array. With that in mind, we do not need to know where this subarray starts or ends.

    Algorithm
    We will start by dividing the problem into smaller pieces. We will take every element in the input array and compute the maximum subarray sum of a subarray ending at this element. Logically, for any element i, the maximum possible sum for a subarray ending at i is either the item i iteself, or the maximum possible sum at element i-1 added to the item i. The higher between the two values would be the max for this item.
    This works because as you traverse the array, the new item you are checking is either improving the current subarray, or it's value by itself is higher that it's value with the current subarray.

    Code

    class Solution {
        public int maxSubArray(int[] nums) {
            int result = Integer.MIN_VALUE;
            int max = 0;
            for(int i=0; i<nums.length;i++)
            {
                max = Math.max(nums[i], max + nums[i]);
                result = Math.max(result, max);
            }
            return result;
        }
    }
    

Log in to reply
 

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