Proof of O(1) space, O(n) running time solution


  • 0
    P

    Let's start with recursive definition of maximum product subarray

    Given an array A[1..n].

    The MPS (maximum product subarray) in A[i..n] is the maximum of

    1. The MPS in A[i..n] starting at A[i] (This is the case when A[i] is included.)
    2. The MPS in A[i+1..n](This is the case when A[i] excluded.)

    The second case can be solved recursively. We need to define the slightly different subproblem MPS in A[i..n] starting at A[i] in the first case.

    The MPS in A[i..n] starting at A[i] is the maximum of

    1. A[i] (MPS in A[i..n] ending at A[i]⁆)
    2. the maximum of A[i]×(MPS in A[i+1..n] starting at A[i+1]) and A[i]×(MinPS in A[i+1..n] starting at A[i+1]) (Not ending at A[i])

    MinPS means minimum product subarray. The second case is correct because A[i] x (any product of subarray) lies within A[i] x MPS and A[i] x MinPS. We can define MinPS in A[i+1..n] starting at A[i+1] similarly as follows.

    The MinPS in A[i..n] starting at A[i] is the minimum of

    1. A[i] (MPS in A[i..n] ending at A[i]⁆)
    2. the minimum of A[i]×(MPS in A[i+1..n] starting at A[i+1]) and A[i]×(MinPS in A[i+1..n] starting at A[i+1]) (Not ending at A[i])

    Let
    MPS(i) denotes MPS in A[i..n],
    MPSsi(i) denotes MPS in A[i..n] starting at A[i],
    and MinPSsi(i) denotes MinPS in A[i..n] starting at A[i].
    The recursive algorithm is as follows.

    MPS(i)
      if i==n
        return A[n]
      else
        return max⁡(MPS(i+1), MPSsi(i))
    MPSsi(i)
      if i==n
        return A[n]
      else
        return max⁡(A[i], max(A[i]×MinPSsi(i+1), A[i]×MPSsi(i+1))
    
    MinPSsi(i)
      if i==n
        return A[n]
      else
        return min(A[i], min(A[i]×MinPSsi(i+1), A[i]×MPSsi(i+1))
    

    Although this recursive algorithm is slow, we can turn it into a dynamic programming easily. Since MPS(i) only depends on MPS(i+1),** MPSsi(i+1)**, and MinPSsi(i+1). We only need to a space of 3 variables and n steps to compute the answer MPS(1). Here is the final dynamic programming solution.

    MPSdynamic(A[1..n])
      MPS = MPSsi = MinPSsi = A[n]
      for i=n−1 down to 1
        tmp = MPSsi
        MPSsi = max(A[i], max(A[i]×MPSsi, A[i]×MinPSsi)
        MinPSsi = min(A[i], min(A[i]×tmp, A[i]×MinPSsi)
        MPS=max⁡(MPS, MPSsi)
    return MPS
    

Log in to reply
 

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