sellingatduke
BAN USERthis is career cup book question
- sellingatduke March 22, 2015With same definition as above, P[i] --> maximum positive product ending at i, N[i] --> minimum negative product ending at i.
if (a[0] != 0) {
P[0] = max(1, a[0]);
N[0] = min(1, a[0]);
} else {
P[0] = 0;
N[0] = 0;
}
if (a[i] < 0) {
P[i] = max (1, N(i-1) * a[i]);
N[i] = min (1, P(i-1) * a[i]);
}
else if (a[i] > 0) {
P[i] = max(1, P[i-1] * a[i]);
N[i] = min(1, N[i-1] * a[i]);
} else {
P[i] = 1;
N[i] = 1;
}
Note that it has not be 1 not -1 for N[i] .. run via an example.
public class SubsetCheck {
public static void main(String[] args) {
Node A = new Node(5, new Node(4, null, null), new Node(7, null, null));
Node B = new Node(6, new Node(5, new Node(4, null,
null), new Node(7, null, null)), new Node(12, new Node(8,
null, null), new Node(10, null, null)));
System.out.println(isSubset(A, B));
}
public static boolean isSubset(Node A, Node B) {
if (A == null)
return true;
if (B == null)
return false;
if (A.value == B.value) {
return (isSubset(A.left, B.left) && isSubset(A.right, B.right))
|| (isSubset(A, B.left) || isSubset(A, B.right));
}
return (isSubset(A, B.left) || isSubset(A, B.right));
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.right = right;
this.left = left;
}
}
void printFibPair(int N) {
- sellingatduke March 22, 2015int pp = 0;
int p = 1;
for (int i=2; i <= N; i++){
System.out.println("[" + pp%10 + " " + p%10 + "]");
current = pp + p;
pp = p;
p = current;
}
}