最大连续数列和

一、题目描述

对于一个有正有负的整数数组，请找出总和最大的连续数列。

给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。

测试样例： [1,2,3,-6,1]返回：6二、解题思路找到原问题与子问题的关系。思路：从下标0开始逐步累加，初始化一个maxsum=0如果累加值大于maxsum则更新maxsum若，累加值为小于等于0时，累加则可以从新的下标开始1：maxhere 存在当前下标前的累加值2：maxsum 存在当前下标前的最大数列和在迭代过程中不断更新maxhere值

int getMaxSum(vector<int> A, int n) { // write code here //maxsum 用来存储最大值，maxhere 下标在此处时的最值。 //动态规划思想 int maxsum=-5,maxhere=0; int i=0; while(i<n) { if(maxhere<=0) { maxhere=A[i]; } else{ maxhere+=A[i]; } if(maxhere>maxsum) { maxsum=maxhere; } i++; } return maxsum; }

 

转载于:https://www.cnblogs.com/zydxx/p/9917498.html

相关资源：JAVA上百实例源码以及开源项目