给定数组,求最大的非邻接子数组之和,复杂度o(n)
例如:
i) 3 2 7 10 结果是 13 ( 3 and 10)
ii) 3 2 5 10 7 结果是 15 (sum of 3, 5 and 7)
对数组 a[i], i = 1, 2, 3, ..., N ,青年人网提示 结果是 f[N]
f[1] = a[1]
f[2] = max (a[1], a[2])
f[n + 2] = max(f[n + 1], f[n] + a[n + 2])
代码:
#include <stdio.h>
int max(int a, int b)
{
return a > b ? a : b;
}
void main()
{
int a[] = {3, 2, 7, 10};
int f1 = a[0];
int f2 = max(a[0], a[1]);
for (int i = 2; i < sizeof(a) / sizeof(a[0]); i++) {
int f3 = max(f2, f1 + a[i]);
f1 = f2;
f2 = f3;
}
printf("%d", f2);
}
责任编辑:小草