动态规划求不相邻的最大子数组和
#include <iostream>#include <string.h>#include <stdlib.h>using namespace std;#define NMax 1000int data[NMax];int table[NMax][2];int GetMaxSubsetSum(int len){memset(table, 0 , sizeof(table));//第0行表示NS，表示该元素未被选中//第一行表示DS，表示该元素被选中table[0][0] = 0;table[0][1] = data[0];//动态规划 过程for (int i = 1; i < len; ++i){table[i][0] = max(table[i-1][1], table[i-1][0]);table[i][1] = table[i-1][0] + data[i];}//打印原始数组for (int i = 0; i < len; ++i)cout << data[i] <<"\t";cout <<endl;//打印NS数组for (int i = 0; i < len; ++i)cout << table[i][0] <<"\t";cout <<endl;//打印DS数组for (int i = 0; i < len; ++i)cout << table[i][1] <<"\t";cout <<endl;//返回整个数组的最大值return max(table[len-1][0], table[len-1][1]);}int main(){int len; cin >> len;if (len <= 0)return 1;for (int i = 0; i < len ; ++i){data[i] = rand()% 10;}cout << GetMaxSubsetSum(len)<<endl;}