Multiply all integer except the current one in Dynamic Programming in Java
public static int[] maxArray(int[] arr){
int len = arr.length;
int[] a1 = new int[len];
int[] a2 = new int[len];
a1[0] = 1;
a2[len-1] = 1;
for(int i = 1; i < len; i++){
a1[i] = arr[i - 1] * a1[i-1];
}
for(int i = 1; i < len; i++){
int ix = len - 1 - i;
a2[ix] = arr[ix + 1] * a2[ix + 1];
}
for(int i = 0; i < len; i++){
a1[i] = a1[i] * a2[i];
}
printArrint(a1);
return a1;
}
// Idea:
2 3 4 5
↓
2 3 4 5
2 3 4 5
2 3 4 5
2 3 4 5
↓
1 3 4 5
2 1 4 5
2 3 1 5
2 3 4 1
↓
1 [3 4 5] ← 1 x [3 4 5]
[2] 1 [4 5] ← [2] x [4 5]
[2 3] 1 [5] ← [2 3] x [5]
[2 3 4] 1 ← [2 3 4] x 1
Generate Down and Up triangles from [2 3 4 5]
{1} ← a1
[2] ← arr
[2 3]
[2 3 4]
for(int i = 1; i < len; i++){
a1[i] = arr[i - 1] * a1[i-1];
}
[ ] [ ] [ ] ← arr
× × ×
[ ] -> [ ] ->[ ] -> [ ] ← a1
[3 4 5]
[4 5]
[5]
1
for(int i = 1; i < len; i++){
int ix = len - 1 - i;
a2[ix] = arr[ix + 1] * a2[ix + 1];
}
Multiply all integer except the current one in Dynamic Programming in C++
/**
$b/cpp/multiply_all_num_except_current.cpp
2 3 4 5
2 3 4 5
2 3 4 5
2 3 4 5
↓
1 1 [3 4 5] 60
2 [2] 1 [4 5] 20
6 [2 3] 1 [5] 5
24 [2 3 4] 1 1
[2] [3] [4] [ ]
↓ ↓ ↓
[1] →[2] →[6] → 24
[ ] [3] [4] [5]
↓ ↓ ↓
[60]←[20]←[5]← [1]
*/
vector multiplyAllArray(vector<int> vec){
int len = vec.size();
vector < int> v1(vec.size(), 0);
vector < int> v2(vec.size(), 0);
v1[0] = 1;
v2[vec.size() - 1] = 1;
for(int i = 1; i < len; i++){
v1[i] = v1[i - 1] * vec[i - 1];
}
for(int i = 1; i < len; i++){
int ix = len - 1 - i;
v2[ix] = v2[ix + 1] * vec[ix + 1];
}
for(int i = 0; i < len; i++){
v1[i] = v1[i]*v2[i];
}
return v1;
}