Who can help me to have a look at my code.


  • 0
    D

    my code can not pass test, but when i test others code with same case, the outputs are the same, could you please help me to have a look. Thanks

    Input: [1,-5,6,-5,2,-4,-5,0,3,2,-4,0,-5,-3,-1,-4,-1,4,1,-1,-3,-1,1,3,-4,-6,-2,5,1,-5,0,-1,-5,0,1,2,6,1,2,-6,5,5,0,1,0,1,1,-1,-1,3,1,0,4,-3,0,4,-4,-1,6,5,5,6,-6,1,1,3,4,3,-1,-3,0,-5,-4,1,5,-2,3,-1,2,1,1,6,0,5,-5,6,-6,3,0,4,-1,3,6,0,-2,0,-1,6,4,1,-5,1,0,1,-1,-1,3,5,5,4,2,5,0,-1,5,2,2,-3,-1,-1,0,-6,-2,-5,1,-2,2,0,0,2,-3,-2,-4,1,1,-4,-3,-1,0,0,1,-3,-2,3,-4,5,2,-1,4,1,5,6,0,1,1,-2,-1,0,-1,-5,5,6,6,-1,-1,0,-4,2,1,3,-5,6,-5,-1,-1,-3,-1,-4,-2,-1,-1,1,-3,-4,0,1,-3,4,3,2,-2,6,-3,-6,-6,-2,-5,1,2,0,-1,0,0,-2,3,-4,2,4,3,-1,3,1,0,2,1,-1,0,5,-1,-3,-6,-5,0,6,6,-6,-5,4,-2,-1,0,4,6,-3,1,-1,0,1,-5,5,-3,-3,-3,-1,-1,4,0,-2,-4,3,5,5,-1,-1,-5,-2,-4,-4,6,0,-3,-1,-5,-3,-1,6,1,-5,-1,0,1,-4,-5,0,0,0,-3,-5,-1,-4,-1,5,5,-4,4,-1,6,-1,1,-1,2,-2,-3,0,1,0,0,-3,0,2,5,-6,-3,-3,3,-4,-2,-6,-1,1,4,4,0,-6,-5,-6,-3,5,-3,1,-4,6,-2,0,-4,-1,0,-1,0,6,-6,0,5,0,1,-3,6,1,-1,1,0,-1,1,-1,-6,-3,4,-1,-4,6,4,-1,-3,2,-6,5,0,4,-2,1,0,4,-2,2,0,0,5,5,-3,4,3,-5,2,2,6,-1,-2,1,-3,1,-1,6,-4,0,0,0,2,-5,-4,2,6,-3,-6,-1,-6,0,0,2,-1,6,-4,-5,-1,0,-3,-3,-1,0,-4,3,1,5,0,2,5,0,4,-5,-1,3,1,-1,-1,1,1,-2,3,5,4,6,2,6,-6,5,2,-3,0,-1,-1,3,1,1,1,-2,-5,3,-1,3,0,-1,3,1,1,-2,6,3,-6,5,-5,-5,0,-2,-3,-3,-4,6,-1,-6,6,-3,-5,1,-1,0,0,1,4,-5,0,1,-2,6,1,-3,-5,0,4,-2,1,-5,-4,0,0,-1,-2,0,2,-2,5,6]
    Output: 93312000 Expected: 31104000

    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    class Solution {
    public:
        int max(int a, int b)
        {
            return a>b? a:b;
        }
        int maxProduct2(int A[], int n) {
            // store the result that is the max we have found so far
            int r = A[0];
    
            // imax/imin stores the max/min product of
            // subarray that ends with the current number A[i]
            for (int i = 1, imax = r, imin = r; i < n; i++) {
                // multiplied by a negative makes big number smaller, small number bigger
                // so we redefine the extremums by swapping them
                if (A[i] < 0)
                    swap(imax, imin);
    
                // max/min product for the current number is either the current number itself
                // or the max/min by the previous number times the current one
                imax = max(A[i], imax * A[i]);
                imin = min(A[i], imin * A[i]);
    
                // the newly computed max value is a candidate for our global result
                r = max(r, imax);
            }
            return r;
        }
        int maxProduct(int A[], int n) {
                int res = A[0];
                vector<vector<int> > intermediate(2, vector<int>( n + 1, 0));
                for(int i = 1; i<= n; ++i)//length
                {
                    for(int j = 0; j <= n - i ; ++j)//start pos
                    {
                        if(i == 1)
                        {
                            intermediate[i%2][j] = A[j];
                        }
                        else
                        {
                            intermediate[i%2][j] = intermediate[(i - 1)%2][j] * A[ j + i - 1];
                        }
                        res = max(res, intermediate[i%2][j]);
    
                    }
                }
                return res;
            }
    };
    int main()
    {
        Solution s;
        int data[] = {1,-5,6,-5,2,-4,-5,0,3,2,-4,0,-5,-3,-1,-4,-1,4,1,-1,-3,-1,1,3,-4,-6,-2,5,1,-5,0,-1,-5,0,1,2,6,1,2,-6,5,5,0,1,0,1,1,-1,-1,3,1,0,4,-3,0,4,-4,-1,6,5,5,6,-6,1,1,3,4,3,-1,-3,0,-5,-4,1,5,-2,3,-1,2,1,1,6,0,5,-5,6,-6,3,0,4,-1,3,6,0,-2,0,-1,6,4,1,-5,1,0,1,-1,-1,3,5,5,4,2,5,0,-1,5,2,2,-3,-1,-1,0,-6,-2,-5,1,-2,2,0,0,2,-3,-2,-4,1,1,-4,-3,-1,0,0,1,-3,-2,3,-4,5,2,-1,4,1,5,6,0,1,1,-2,-1,0,-1,-5,5,6,6,-1,-1,0,-4,2,1,3,-5,6,-5,-1,-1,-3,-1,-4,-2,-1,-1,1,-3,-4,0,1,-3,4,3,2,-2,6,-3,-6,-6,-2,-5,1,2,0,-1,0,0,-2,3,-4,2,4,3,-1,3,1,0,2,1,-1,0,5,-1,-3,-6,-5,0,6,6,-6,-5,4,-2,-1,0,4,6,-3,1,-1,0,1,-5,5,-3,-3,-3,-1,-1,4,0,-2,-4,3,5,5,-1,-1,-5,-2,-4,-4,6,0,-3,-1,-5,-3,-1,6,1,-5,-1,0,1,-4,-5,0,0,0,-3,-5,-1,-4,-1,5,5,-4,4,-1,6,-1,1,-1,2,-2,-3,0,1,0,0,-3,0,2,5,-6,-3,-3,3,-4,-2,-6,-1,1,4,4,0,-6,-5,-6,-3,5,-3,1,-4,6,-2,0,-4,-1,0,-1,0,6,-6,0,5,0,1,-3,6,1,-1,1,0,-1,1,-1,-6,-3,4,-1,-4,6,4,-1,-3,2,-6,5,0,4,-2,1,0,4,-2,2,0,0,5,5,-3,4,3,-5,2,2,6,-1,-2,1,-3,1,-1,6,-4,0,0,0,2,-5,-4,2,6,-3,-6,-1,-6,0,0,2,-1,6,-4,-5,-1,0,-3,-3,-1,0,-4,3,1,5,0,2,5,0,4,-5,-1,3,1,-1,-1,1,1,-2,3,5,4,6,2,6,-6,5,2,-3,0,-1,-1,3,1,1,1,-2,-5,3,-1,3,0,-1,3,1,1,-2,6,3,-6,5,-5,-5,0,-2,-3,-3,-4,6,-1,-6,6,-3,-5,1,-1,0,0,1,4,-5,0,1,-2,6,1,-3,-5,0,4,-2,1,-5,-4,0,0,-1,-2,0,2,-2,5,6};
        int len = sizeof(data)/sizeof(int);
        cout << s.maxProduct2(data, len)<<endl;
        cout << s.maxProduct(data, len)<<endl;
        return 0;
    }

  • 0
    E

    Local test: maxProduct() and maxProduct2() give same output 31104000;

    OJ test: maxProduct() TLE(at another test case), maxProduct()2 AC;

    maxProduct() actually check every possible products and find the maximum, which is O(n^2), although somewhat space-saving. You should switch to DP.


Log in to reply
 

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