求一循环数组的最大子数组的和

矫情吗；* 2021-12-15 17:13 219阅读 0赞

解题思路：

当数组是首尾相连时，求连续子数组最大和的方法可以归纳如下：

1.将原数组进行扩充，即假设原数组为\{1,2,-3,4,5\}，则扩充相当于\{1,2,-3,4,5,1,2,-3,4,5\}

2.利用上述的解法在扩充后的数组进行遍历求其连续子数组的最大和，不过要做一些小改动，即保证子数组的长度在原数组的长度范围之内。这样求出来的结果即是原数组首尾相连后，连续子数组的最大和。

\#include<iostream>  
\#include<cmath>  
using namespace std;  
void main()  
\{  
int a\[25000\],i,j,n,MaxSum,k,m,h,p;  
int f=0;  
int b\[10\],d\[10\];  
  
cout<<"请输入数组中数字的个数"<<endl;  
cin>>n;  
cout<<"请输入数组"<<endl;  
for(i=0;i<n;i++)  
\{  
cin>>a\[i\];  
\}  
for(i=n;i<2\*n;i++)  
\{  
a\[i\]=a\[i-n\];  
\}  
cout<<endl;  
  
  
  
for(i=0;i<n;i++)  
\{  
k=0;  
MaxSum=0;  
h=i;  
for(j=i;j<i+n;j++) \{ k += a\[j\];  
if(k > MaxSum)  
\{  
MaxSum = k;  
h=j;  
\}  
  
if(k < 0)  
\{  
k = 0;  
\}  
\}  
d\[i\]=h;  
b\[i\]=MaxSum;  
  
\}  
int c=b\[0\];  
m=0;  
h=0;  
for(i=1;i<n;i++)  
\{  
if(c<=b\[i\])  
\{  
c=b\[i\];  
m=i;  
h=d\[i\];  
\}  
\}  
p=h-n+1;  
if(p<=0)  
\{ p=n;\}  
cout<<"从第"<<m+1<<"个到第"<<p<<"个"<<endl;  
cout<<"最大子数组为"<<endl;  
for(i=m;i<h+1;i++)  
\{ cout<<a\[i\]<<" ";\}  
cout<<endl;  
cout<<"最大子数组之和为"<<c<<endl;  
  
\}

![131104141514603.png][]

五 总结反思

对于数组的理解更加深刻，团队合作很重要。

转载于:https://www.cnblogs.com/LJT666/p/4428253.html

[131104141514603.png]: /images/20211215/60b7fd713486404a948c15608c731634.png

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子数组和

/ 输入一个整数数组nums，请在其中找一个和最大的子数组动态规划定义dp数组：dp[i]是以num[i]结尾的最大子数组和 / public cla

矫情吗；*/ 2022年10月29日 10:28/ 0 赞/ 179 阅读

相关最大子数组和

/ 输入一个整数数组nums，请你在其中找一个和最大的子数组，返回这个子数组的和 dp[i]表示以nums[i]的最大子数组和状态 / public c

青旅半醒/ 2022年10月27日 13:49/ 0 赞/ 193 阅读

相关求连续子数组的最大和

[求连续子数组的最大和][Link 1] 整理自 [ http://blog.csdn.net/v\_JULY\_v/article/details/6444021][h

阳光穿透心脏的1/2处/ 2022年09月21日 13:11/ 0 赞/ 177 阅读

相关求连续子数组的最大和

文章目录求连续子数组的最大和题目描述题目链接解题思路求连续子数组的最大和题目描述

蔚落/ 2022年09月07日 14:42/ 0 赞/ 194 阅读

相关【动态规划】求一维子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如，输

傷城~/ 2022年08月09日 00:59/ 0 赞/ 186 阅读

相关求子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为

- 日理万妓/ 2022年08月02日 01:18/ 0 赞/ 186 阅读

相关求数组的子数组和的最大值

来源：编程之美2.24 一些典型的测试用例： \[1，-2,3,5，-3,2\] max=8 \[0,-2,3,5,-1,2\] max =9 \[-

秒速五厘米/ 2022年05月21日 05:52/ 0 赞/ 194 阅读

相关算法求子数组的最大和 C

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

港控/mmm°/ 2022年04月18日 02:27/ 0 赞/ 161 阅读

相关求连续子数组的最大和（C++）

出处：[https://www.cnblogs.com/waytofall/archive/2012/04/10/2439820.html][https_www.cnblogs

迈不过友情╰/ 2022年03月27日 05:55/ 0 赞/ 209 阅读

相关求一循环数组的最大子数组的和

解题思路：当数组是首尾相连时，求连续子数组最大和的方法可以归纳如下： 1.将原数组进行扩充，即假设原数组为\{1,2,-3,4,5\}，则扩充相当于\{1,2,-3,4,

矫情吗；*/ 2021年12月15日 17:13/ 0 赞/ 220 阅读