最大子段和 - 洛谷

最大子段和

题目描述

给出一个长度为 n的序列a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度n。

第二行有n个整数，第i个整数表示序列的第 i个数字 a_i。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入
7
2 -4 3 -1 2 -4 3
样例输出
4

提示

样例 1 解释

选取[3, 5]子段 {3, -1, 2}，其和为 4。

数据规模与约定

- 对于 40% 的数据，保证 n <=2 <=10^3。
- 对于 100%的数据，保证 1 <= n <=2*10^5，-10^4<=a_i <=10^4。

代码区：

#include<stdio.h>
#include<stdlib.h>
int main(){
	int n;
	scanf("%d",&n);
	long int *arr=(long int*)malloc(n*sizeof(long int));
	for(int i=0;i<n;i++){
		scanf("%ld",&arr[i]);
	}
	long int max=arr[0];
	long int sum=0;
	for(int i=0;i<n;i++){
		sum+=arr[i];
		if(sum>max){
   			max=sum;
		}
		if(sum<0){
			sum=0;
		}
	}
	printf("%ld",max);

	return 0;
}

欢迎各位读者提出意见。

（菜菜洛谷奋斗小日记）