interviewbit/MAXSPPROD.cpp at master · suri321/interviewbit · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int Solution::maxSpecialProduct(vector<int> &A) {
    long long int n=A.size();
    long long int arr[n],arr2[n];
    memset(arr,0,sizeof(arr));
    memset(arr2,0,sizeof(arr2));

    for(int i=1;i<n-1;i++)
    {
        int j=i-1;
        if(A[i]<A[i-1])
            arr[i]=i-1;
        else
        {
            while(j>0 and A[i]>=A[j])
            {
                j=arr[j];
            }
            arr[i]=j;
        }
    }
    arr2[n-1]=n-1;
    for(int i=n-2;i>0;i--)
    {
        int j=i+1;
        if(A[i]<A[i+1])
            arr2[i]=i+1;
        else
        {
            while(j<n-1 and A[i]>=A[j] )
            {
                j=arr2[j];
                if(j==0)
                    break;
            }
            if(j==0)
                arr2[i]=0;
            else if(j==n-1 and A[i]>=A[j])
                arr2[i]=0;
            else
                arr2[i]=j;
        }
    }
    long long int ans=0;
    for(int i=1;i<n-1;i++)
    {
        long long int temp=(arr[i]*arr2[i]);
        if(ans<temp)
            ans=temp;
    }
    return ans%1000000007;
}