Very simple Java solution with explanations


  • 0
    B

    Hi,

    I've seen solutions with Dynamic Programming and other complicated stuff. Nothing so complex is needed here.

    To solve this problem, imagine that you're going mountain hiking. Positive numbers represent ascending paths and negative numbers represent descending paths. Finding the maximum subarray is equivalent to find the part of the path with the highest difference in height.

    So, you start from the ground and add values to get your current height. The trick to notice here is that if you go below the ground, you can just ignore the previous paths and start from the ground again. That's because going below the ground means that you have reached the best minimum so far and if there's a better path ahead, then it must start from here.

    Here's the corresponding code

    public class Solution {
        public int maxSubArray(int[] nums) {
            int max = Integer.MIN_VALUE;    // negative "infinity", in case all values are negative
            int sum = 0;                    // start at ground level
            for (int n : nums) {
                sum = Math.max(sum, 0) + n; // difference in height from the lowest point
                max = Math.max(max, sum);   // only keep the highest one
            }
            return max;
        }
    }
    

Log in to reply
 

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