当前位置: 首页> 文章列表> c++求连续子数组的最大和

c++求连续子数组的最大和

最新
2021-01-06 23:00:09 112
飞一样的编程
擅长邻域:Java,MySQL,Linux,nginx

技术小结:

今天给大家分享得主题是:求子数组得最大和 - C++

/*
* 求子数组得最大和 - C++ - by www.jf3q.com
*
* 题目:输入一个整形数组,数组里有正数也有负数。数组中连续得一个或多个整数组成一个子数组,每个子数组都有一个和。
* 求所有子数组得和得最大值。要求时间复杂度为O(n)。
* 例如输入得数组为5, -22, 13, 0, 45, -7, 42, -19;和最大得子数组为13, 0, 45, -7, 42;因此输出为该子数组得和为93。
*
* Answer: A traditional greedy approach.
*/

#include <iostream>
#include <stdio.h>

using namespace std;

int MaxSum(int *a, const int size) {
if (size <= 0) {
length_error("Error, wrong array size.");
}

int sum = 0;
int max = -(1 << 31);
int cur = 0;

while (cur < size) {
sum += a[cur++];

if (sum > max) {
max = sum;
}

if (sum < 0) {
sum = 0;
}
}

return max;
}

int main(int argc, char *argv[]) {
int a[] = {5, -22, 13, 0, 45, -7, 42, -19};
cout << MaxSum(a, 8) << endl;

return 0;
}

// Output:
/*
行,今天就给大家分享到这里吧,您的一份支持就是我最大的动力,最后打个小广告,我们程序员在学习和工作中或多或少会遇到一些比较棘手的问题,也就所谓的一时半会解决不了的bug,可以来杰凡IT问答平台上提问,平台上大佬很多可以快速给你一对一解决问题,有需要的朋友可以去关注下,平台网址: https://www.jf3q.com
*/

写的很好呢,我要分享哦!

此处可发布评论

    暂无评论
    联系大神 有偿问答

    榜上有名--赚钱榜

    第一时间了解动态

    关注我们