gmetrofun
BAN USERLinear solution with constant additional memory in JS:
var A = [1, 5, 3, 9, 4], partial = [], i;
partial[0] = Math.max(A[0], 0);
partial[1] = Math.max(partial[0], Math.max(A[1], 0));
for (i = 2; i < A.length; i++) {
partial[i % 2] = Math.max(partial[(i - 1) % 2], partial[(i - 2) % 2] + Math.max(A[i], 0));
}
Here is my recursive solution in javascript. Complexity is 4^(n-1) because in the worst case we simply generate all possible combinations of – + * /
function eveluate(numbers, N) {
var remainingNumbers, firstNumber, secondNumber;
if (numbers.length === 0) {
return false;
} else if (numbers.length === 1) {
return Math.abs(numbers[0] - N) < 0.00001;
} else {
remainingNumbers = numbers.slice(1);
firstNumber = numbers[0];
secondNumber = remainingNumbers[0];
if (eveluate(remainingNumbers, N - firstNumber)) {
return true;
} else {
remainingNumbers[0] = - secondNumber;
if (eveluate(remainingNumbers, N - firstNumber)) {
return true;
} else {
remainingNumbers[0] = firstNumber * secondNumber;
if (eveluate(remainingNumbers, N)) {
return true;
} else {
remainingNumbers[0] = firstNumber / secondNumber;
if (eveluate(remainingNumbers, N)) {
return true;
}
}
}
}
}
}
We can build a "Trie", where every edge will represent alphanumeric symbols from pattern.
'+' and '*' will result in a tree loops. After building a trie, we can traverse it recursively following every loop, until the whole string is matched.
- gmetrofun September 25, 2013