Algorithm_最大子数组问题 发表于 2018-05-06 | 分类于 ACM | 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647// MaxValueChildArray.cpp : 定义控制台应用程序的入口点。/**最大子数组问题:求一个数组的子数组,要求子数组的元素的和在所有的子数组中最大时间复杂度O(n)这个问题调用了两次动态规划,比较难@author:XiaJun@date May 6th,2018**/#include "stdafx.h"int main(){ int arr[11] = {-2,6,5,-9,1,-3,9,12,-23,18,2}; //以边界为终点的最大子数组和要求的最大子数组 int bound[11],result[11]; //初始化 int i = 0,j = 0; for(i = 0;i < 11;i++) { bound[i] = 0; result[i] = 0; } //利用动态规划求边界为终点(当前的遍历索引在子数组的边界)的最大子数组 int curMax = arr[0]; bound[0] = arr[0]; for(i = 1;i < 11;i++) { if(curMax <= 0) { curMax = arr[i]; } else { curMax += arr[i]; } bound[i] = curMax; } //求最终的最大子数组 int maxValue = arr[0]; result[0] = arr[0]; for(i = 1;i < 11;i++) { if(arr[i] > 0) {//小于0不用考虑,这种情况下最大子数组的和不变 if(arr[i]+bound[i-1] > maxValue) { maxValue = arr[i]+bound[i-1];//该元素被包含在了最大子数组中 } } } printf("最大子数组的和是:%d\n",maxValue); return 0;}