Will
BAN USERThank YD for reminding. I misunderstood the question.
Here's an O(n) solution for max product (inspired by the "longest valid parentheses" problem):
static int product(int A[], int begin, int end)
{
int i, step, mh, ma;
step = begin>end?-1:1;
ma = A[begin]; mh = 1;
for (i = begin; i != end; i += step) {
mh *= A[i];
if (mh > ma)
ma = mh;
if (A[i] == 0)
mh = 1;
}
return ma;
}
int max_subarray_product(int A[], int n)
{
int x, y;
x = product(A, 0, n-1);
y = product(A, n-1, 0);
return x>y?x:y;
}
Booting a device may need several stages:
1. boot ROM (in processor)
2. first stage boot loader
3. second stage boot loader
4. kernel
After all, we want to run the kernel. Booting process starts from 'boot ROM' in a processor, if the 'boot ROM' can load and run kernel, we can remove all other boot loaders. But, most processor's 'boot ROM' cannot do this, they can only load simple boot loader code from special area. The simple boot loader can then load a complex boot loader or load kernel directly. Complex boot loader has more helpful functions for development, but it's not necessary for a shipped product.
- Will August 20, 2013assume that all nodes are stored in an array or a list:
// mark non-leaf nodes
for each node do
mark its direct parent node
end
// get max length
for each node do
if node is marked then //non-leaf
skip
else // leaf
visit all parent nodes until root and count the length
keep the max length
end
end
the worst case time complexity is O(nlogn)
- Will August 19, 2013This looks a little bit like a zigzag problem:
1 9
2 810
3 7 11
4 6 12
5 13...
The length of the repeated pattern is 8, so
x = n%8
if x == 0 then
return 2
else if x < 5 then
return x
else
return 10-x
end
or, we can count from 0:
0 8 16
1 79 15
2 6 10 14
3 5 11 13
4 12
and
x = (n-1)%8
if x < 5 then
return x+1
else
return 9-x
end
in celebrity problem, i must equals j, this one doesn't have such an assumption.
- Will September 14, 2013