//根據(jù)左積*右積的思路
class Solution {
public:
    vector<int> multiply(const vector<int>& a) {
        int n=a.size();
        vector<int> res(a.size());

        vector<int> dp1(n,1);   //左積
        vector<int> dp2(n,1);   //右積
        for(int i=1;i<n;i++)
        {
            dp1[i]=dp1[i-1]*a[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            dp2[i]=dp2[i+1]*a[i+1];
        }
        for(int i=0;i<n;i++)
        {
            res[i]=dp1[i]*dp2[i];
        }
        return res;
    }
};