最大子列和(C语言)

最大子列和(C语言),第1张

最大子列和(C语言) (3)动态规划

算法思想:
前提:假设输入的数组为[-1,3,-2,4,-6,1,6,-1]
(1)将连续的数字看成是一个整体
(2)若该整体为负数,向后遍历都不是最大的,拿上面的例子,第一个数字是-1,往后遍历-1+3=2,确实是正数,但是后面的3是比2大的,就得抛弃-1,所以前面是负数后面就是要抛弃掉的
(3)把前面的整体抛弃掉是不存在把最大值给漏掉的可能的,因为代码sum=0只是把sum的重置了0,max值还是前面最大的子列和,只有在后面遇到比max大的才会更新

#include

int maxSubArray(int A[],int N);
int main(){
	int N;//N个数 
	scanf("%d",&N);
	//用数组来存储数据 
	int A[N];
	int i;
	for(i = 0;i < N;i++){
		scanf("%d",&A[i]);
	}
	int result = maxSubArray(A,N);
	printf("%d",result);
	return 0;
	
}

int maxSubArray(int A[],int N){
	int max = 0;
	int sum = 0;
	int i;
	for(i = 0;i < N;i++){
		sum = sum + A[i];
		if(sum > 0){
			if(sum > max){
				max = sum;
			}
		}
		else{
			sum = 0;
		}
	}
	return max;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5714164.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存