Hackerrank "Bricks Game"

Problem URL

This is the solution I came up with the minimax problem stated above. I did a top-down recursive approach with memoization, and I think this should be \$O(n)\$, since we are filling out a memoization table with \$n\$ elements, with constant number of operations per each recursive call. Nevertheless, I am getting timeout errors for something like n = 1000, which probably indicates this is not an \$O(n)\$ implementation after all.

Can I get some advice on what my misunderstanding is?

```
#include
#include
#include
#include
#include
using namespace std;

int pick(vector stack, int idx, int end, vector memo){
// Check if memoized.
if (memo[idx] != -1) return memo[idx];

int last = end - 1;
// Base Case
// Nothing to Pick.
if(idx > last) return 0;
// Only one brick.
else if(idx > last - 1) return stack[last];
// Two bricks.
else if(idx > last - 2) return stack[last] + stack[last - 1];
// Three bricks.
else if(idx > last - 3) return stack[last] + stack[last - 1] + stack[last - 2];

int case1,case2,case3;
int p2,p3,p4,p5,p6;

p2 = pick(stack,idx+2,end,memo);
p3 = pick(stack,idx+3,end,memo);
p4 = pick(stack,idx+4,end,memo);
p5 = pick(stack,idx+5,end,memo);
p6 = pick(stack,idx+6,end,memo);

case1 = stack[idx] +
min({p2,p3,p4});

case2 = stack[idx] +
stack[idx+1] +
min({p3,p4,p5});

case3 = stack[idx] +
stack[idx+1] +
stack[idx+2] +
min({p4,p5,p6});

memo[idx] = max({case1,case2,case3});

return memo[idx];
}

int main() {
/ Enter your code here. Read input from STDIN. Print output to STDOUT /
int tests;
int stackSize;
vector stack(100000,0),memo(100000,-1);
cin >> tests;
for(int test = 0 ;test > stackSize;
for(int i=0;i> stack[i];
cout << pick(stack,0,stackSize,memo) << endl;
fill(memo.begin(),memo.begin() + stackSize ,

You are passing the stack vector by value, which means that on each call to pick, you will incur O(n) time to copy the vectors. You need to pass by reference or const reference.

See my answer here to another question with the same problem:
https://codereview.stackexchange.com/a/144084/36120

StackExchange Code Review Q#144829, answer score: 3