c - 求数组子序列的最大和的算法是什么？

Question

有一个包含元素 {5,30,99,60,5,10} 的一维数组。从该数组中，1 个子序列为 5、99 和 10，其总和为 114。其他子序列的总和小于 114。子序列中的两个元素不应连续，即 {5, 30 和 60} 不是有效的子序列(对于此问题)。它可以是 {5, 99, 5} 或 {30, 60, 10} 等。该数组不包含负数。什么方法是计算这个最大总和的正确方法？我正在尝试用 C 语言实现它。

Answer 1

递归是你的 friend

总和是最大值

5 + {99, 60, 5, 10} 的 maxSum

或者放弃 5 而选择 30 并且

30 + {60, 5, 10} 的 maxSum

假设您没有任何负数，则应使用 5 或 30，然后使用剩余的序列。丢弃两者是没有意义的。