CareerCup

edited, added corner cases and updated recursion
@tryingtolearn: yes it's dp, but watch out your recursion, it has some flaws, did you verify with examples?

''' 
Assumption: if all are negative, we select empty set, 
sum 0 > anything negative
Solution:
---------
Recursion:
         / max(0, value(0)), for i = 0
dp(i) = |  max(dp(0), value(1)), for i = 1
         \ max(dp(i - 2) + value(i), dp(i - 1)), for i > 1 
Optimization:
-------------
since the recursion only accesses dp(i-2) and dp(i-1) we can get around the dp-array
'''
def maxboxes(values):
    if(len(values) == 0): return 0
    dp = [0 for i in range(len(values))]
    dp[0] = max(0, values[0])
    if(len(values) == 1): return dp[0]
    dp[1] = max(dp[0], values[1])
    for i in range(2, len(values)):        
        dp[i] = max(dp[i-2] + values[i], dp[i-1])
    return dp[len(values)-1]

# optimized to remove dp-array
def maxboxesOpt(values):
    if(len(values) == 0): return 0
    dp0 = max(0, values[0])
    if(len(values) == 1): return dp0
    dp1 = max(dp0, values[1])
    for i in range(2, len(values)):        
        tmp = dp1
        dp1 = max(dp0 + values[i], dp1)
        dp0 = tmp
    return dp1

print(maxboxesOpt([0,1,-2,3])) # should be 4
print(maxboxesOpt([8,1,-1,2,2,10])) # should be 20
print(maxboxesOpt([10,0,0,0,20])) # should be 30
print(maxboxesOpt([-1, -2, -3])) # should be 0 
print(maxboxesOpt([])) # should be 0
print(maxboxesOpt([-2])) # should be 0
print(maxboxesOpt([99])) # should be 99

@Chrisk, thank you for pointing out, my recursion is wrong. I apologize I wrote it without thinking though. I have a question in your solution
print(maxboxes([8,1,-1,2,2,10])) # should be 18, should not this be
20, { 8,2, 10} =20?

@ChrisK, your solution is not working for input containing all negatives, e.g. [-1,-2,-3]. Also, there is no need in dp list.

Here is my solution with O(n) time / O(1) memory. I hope it covers all corner cases :)

class Main {
  public static void main(String[] args) {
    System.out.println(solve(new int[] {0,1,-2,3}));      // -> 1+3 = 4
    System.out.println(solve(new int[] {8,1,-1,2,2,10})); // -> 8+2+10 = 20
    System.out.println(solve(new int[] {10,0,0,0,20}));   // -> 10+20 = 30
    System.out.println(solve(new int[] {-1,-2,-3}));      // -> all negatives -> 0
  }
  
  private static int solve(int[] boxes) {
    if (boxes.length == 0) return 0;
    if (boxes.length == 1) return max(0, boxes[0]);
    
    int box2 = boxes[0];
    int box1 = boxes[1];
    for (int i = 2; i < boxes.length; i++) {
      int curr = box2 + boxes[i];
      box2 = max(box2, box1);
      box1 = max(box1, curr);
    }
    return max(box1, max(box2, 0));
  }
}

@petrov4feedly, thanks for providing optimized version without memorization,a minor bug that I see,
for e,g -3, -2 , -1 int curr = box2 + boxes[i]; this needs to be changed to int curr = max(box2 + boxes[i], boxes[I]))? or else your solution gives out -2

@petro4feedly , i had a question. What if we have boxes something like {8,9,1,1} then what is supposed to be the answer. Ans which variable gives us the answer

Am i reading the question wrong? It tells the boxes need to be sequential and also saying we cannot use a box next to what is selected.

so i need to first sort the list and then smart select boxes so that the sum is the maximum possible.

but if I follow these rules many of answers above looks wrong. what am i missing here?

Looks like I miss something here... I see answers and they looks good. but did not get how the conditions are met in the logic.

what we need to do : Select the numbers in order to have the maximum sum from collection.

Limitations.
1) sequentially placed boxes
2) Cannot select adjacent box to it, but can select any other.

So once I select a box i cannot select next one. so essentially I can skip one box but if a select a box i cannot select next box to it.

How these conditions are met.

10, 0, 0, 0, 20 -> 0, 0, 0, 10, 20 = 30? but it fails the rule since if i select 10 i cannot take 20.
8, 1, -1, 2, 20, 10 - > -1, 1, 2, 8, 10, 20 = 28. Yes i get the answer. but how it is coming in?
-1, -2, -3 = is this should be -1 and not zero since the maximum value must be the sum of one or more values from array?

public int maxProfit(int[] nums) {
        int n = nums.length;
        int even = 0;
        int odd = 0;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                even = Math.max(odd, even + nums[i]);
            } else {
                odd = Math.max(even, odd + nums[i]);
            }
        }

        return Math.max(even, odd);
    }

int maxSum(const vector<int>& v)
{
    const auto size = v.size();
    
    if(size == 1)
    {
        return v[0];
    }
    
    if(size == 2)
    {
        return max(v[0], v[1]);
    }

    // Assuming no integer overflow happens, i.e. sum variable will not overflow
    int sum = (1 << (8 * sizeof(int) - 1));

    for(auto iter = v.begin(); iter != prev(v.end(), 2); ++iter)
    {
        vector<int> v1(v.end() - iter - 2);

        copy(next(iter, 2), v.end(), v1.begin());

        sum = max(sum, *iter + maxSum(v1));
    }

    return sum;
}

this dynamic programming problem
f(m) is max value at index m
f(m) = max{ f(m-1) +value(m), f(m-1)}