夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
最大子数组
#include<bits/stdc++.h>
using namespace std;
int l,r;
int maxSubArraySum(int x[], int n) 
{
	int maxSum = 0;//最大值 
	int thisSum = 0;//当前最大值,临时 
	l = 0;//起始下标 
	r = 0;//终点下标 
	for (int i = 0; i < n; i++) {
		thisSum += x[i];
		if (thisSum > maxSum){
			maxSum = thisSum;
			r = i;
		}
		if (thisSum < 0){
			thisSum = 0;
			if(i <= n - 2 && x[i+1] > 0){//修改起点特判是否越界,以及下一元素的值是否为正 
				l = i + 1;
			}
		}
			
	}
	//如果最大子数组不在数组里面的话(数组元素全部<=0),l,r赋值为-1
	if(l == 0 && r == 0 && x[0] <= 0){
		l = -1;
		r = -1;
	}
	return maxSum;
}
int main()
{
	int n,x[2000];
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>x[i];
	cout<<maxSubArraySum(x,n)<<endl;
	cout<<l<<" "<<r;
}

样例
11
-1 4 6 -3 7 -3 -3 9 -7 6 13


时间复杂度O(n)

暂无评论

发送评论 编辑评论


				
上一篇