Why does this concise solution work?


  • 0
    M

    Any ideas on why this algorithm is correct?

        if(nums == null || nums.Length == 0)
        {
            throw new ArgumentException("Invalid input");
        }
        
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        
        for(int i = 1; i < nums.Length; i++)
        {
            int prev_max = max;
            int prev_min = min;
            max = Math.Max(nums[i],Math.Max(prev_max*nums[i], prev_min*nums[i]));
            min = Math.Min(nums[i],Math.Min(prev_max*nums[i], prev_min*nums[i]));
            result = Math.Max(result, max);
        }
        
        return result;

  • 0
    H

    I like this solution!
    instead of using sorting out the max integer in max_array after the loop, it decides to keep track of the max value in every iteration.


  • 0
    K

    It is accounting for negative values. max will store the maximum value seen till now, and if negative values exist in the array, min will keep track of the smallest negative number. To give you an example, consider the following input array :

    [1, -10, 2, -1]

    Initially, max = 1, min = 1, and result = 1.

    In the first iteration of the for loop, max = -10, min = -10, and result is still 1.

    In the second iteration, max = 2, min = -10, and result is 2.

    In the third iteration, max = 10, min = -2, and result is 10.

    This is because even though -10 is small, -10 * -1 is larger than the product of contiguous positive numbers.


  • 0
    F

    Your second iteration is wrong. it should be max = 2 and min = -20, thus the final result will be 20


Log in to reply
 

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