Time complexity of my backtracking to find the optimal solution of the maximum sum non adjacent

Question

I'm trying to do dynamic programming backtracking of maximum sum of non adjacent elements to construct the optimal solution to get the max sum.

Background:

Say if input list is [1,2,3,4,5]

The memoization should be [1,2,4,6,9]

And my maximum sum is 9, right?

My solution:

1. I find the first occurence of the max sum in memo (as we may not choose the last item) [this is O(N)]

2. Then I find the previous item chosen by using this formula:

   max_sum -= a_list[index]

As in this example, 9 - 5 = 4, which 4 is on index 2, we can say that the previous item chosen is "3" which is also on the index 2 in the input list.

3. I find the first occurence of 4 which is on index 2 (I find the first occurrence because of the same concept in step 1 as we may have not chosen that item in some cases where there are multiple same amounts together) [Also O(N) but...]

The issue:

The third step of my solution is done in a while loop, let's say the non adjacent constraint is 1, the max amount we have to backtrack when the length of list is 5 is 3 times, approx N//2 times.

But the 3rd step, uses Python's index function to find the first occurence of the previous_sum [which is O(N)] memo.index(that_previous_sum)

So the total time complexity is about O(N//2 * N)

Which is O(N^2) !!!

Am I correct on the time complexity? Or am I wrong? Is there a more efficient way to backtrack the memoization list?

P.S. Sorry for the formatting if I done it wrong, thanks!

Answer 1

Solved:

1. I looped from behind checking if the item in front is same or not
2. If it's same, means it's not first occurrence. If not, it's first occurrence.
3. Tada! No Python's index function to find from the first index! We find it now from the back

So the total time complexity is about O(N//2 * N)

Now O(N//2 + 1), which is O(N).