首页 > 代码库 > 连续子数组的最大和
连续子数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或者连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
分析：首先需要考虑的条件：数组里有正数也有负数，根据这个条件，从数组第一个元素开始，temp累计相加，当temp增加时，我们就将temp赋值给sum。当temp为小于0 ，我们就将temp归为0，但是此时sum还是保存之前的最大值。temp接下来继续这样累加。。
#include "stdafx.h"#include <iostream>using namespace std;int FindMaxSum(int pData[],int length){ if (pData =http://www.mamicode.com/= NULL || length <= 0) return 0; int sum = 0; int temp = 0; for (int i = 0; i < length; ++i) { temp += pData[i]; if (temp>sum) sum = temp; if (temp <= 0) temp = 0; } return sum;}int _tmain(int argc, _TCHAR* argv[]){ int data[] = { 1,-7,4,3,-2,5 }; cout << FindMaxSum(data, 6) << endl; return 0;}
这题还可以用动态规划去做。
判断最后一个数字之外的和是大于0 还是小于0.动态规划总是从最后一个开始入手。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。