c программирование головоломки

Question

Учитывая массив, все элементы которого являются положительными числами, найдите максимальную сумму подпоследовательности с ограничением, что никакие 2 числа в последовательности не должны быть смежными в массиве. Таким образом, 3 2 7 10 должно возвращать 13 (сумма 3 и 10) или 3 2 5 10 7 должно возвращать 15 (сумма 3, 5 и 7).

Я попробовал использовать все возможные разрешенные суммы, а затем найти максимум (метод грубой силы), но есть ли лучший метод. Например, для [3 2 7 10] я суммирую 3,7 и 2,10 и беру максимум.

---

Больше примеров:

• [ 3 , 2, 7 , 1]: возврат 10
• [ 6 , 2, 1, 4 ]: возврат 10
• [ 8 , 9, 5 , 1]: возврат 13
• [29, 77 , 16]: возврат 77
• [ 29 , 44, 16 ]: возврат 45

Answer 1

sum[0] = 0;
sum[1] = 0;

for(i = 0; i < arraylength; i++) 
    sum[i & 1] += array[i];

printf("sum = %u\n", MAX(sum[0], sum[1]));
printf("homework completed\n");