//分治算法
//题目：给定一个包含整数n的数组，请确定该数组中元素总和的最大可能值
//
//问题函数定义：
//
//cpp
//int maxSum(std::vector& nums);
//裁判测试程序样例：
//
//cpp
#include
#include
using namespace std;

//动态规划解

int maxSum(vector nums) {
vector dp(nums.size());
将dp数组的第一个元素赋值为nums向量的第一个元素。
将dp数组的第二个元素赋值为nums向量前两个元素的最大值。
for循环从索引2开始遍历：
在i大于等于2的情况下，默认情况下取前一个位置的最大值；
如果加上当前nums[i]与前两个位置之和更大，则更新当前最大值。
}
返回最后一个计算得到的总最大值。
}
int main() {
vector nums = { 1, 2, 3, 4, 5 };
cout << maxSum(nums) << endl;
return 0;
}
//输入样例：
//
//1 2 3 4 5
//输出样例：
//
//9

//分治解

#include