构建乘积数组
C++，类似于动态规划应该。
利用两个数组，记录每一个位置之前所有元素的乘积和之后所有元素的乘积。
而本题要求的正是每个元素除了自己以外所有元素的乘积，将之前和之后相乘就行了。
但实际上，这两个数组是多余的，只要用返回答案的数组来记录就行了。第一遍遍历可以得到每个元素之前所有元素的乘积，第二遍从后往前遍历，记录每个元素之后的所有元素的乘积，如果直接乘会覆盖，所有定义一个临时变量记录之前遍历的一个就行。
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> ans(A.size(), 1);
if (ans.empty()) return ans;
for (int i = 1; i < ans.size(); i++)
ans[i] = ans[i-1] * A[i - 1];
int temp = 1;
for (int i = ans.size() - 1; i >= 1; i--) {
ans[i] = temp * ans[i];
temp *= A[i];
}
ans[0] = temp;
return ans;
}
};
