一个有 N个元素的整型数组，求该数组的各个子数组中，子数组之和的最大值是多少？例如数组 a[6]={-2,5,3,-6,4,-8,6};则子数组之和的最大值是 8(即 a[1]+a[2])。

Dear 丶 2023-06-30 08:48 16阅读 0赞

一个有 N个元素的整型数组，求该数组的各个子数组中，子数组之和的最大值是多少？ 例如数组 a\[6\]=\{-2,5,3,-6,4,-8,6\};则子数组之和的最大值是 8(即 a\[1\]+a\[2\])。

更多资料请点击：[我的目录][Link 1]

方法一：

#include <stdio.h>
    
    int i ,j , N,max;
    
    int main()
    { 
    	printf("请输入数组大小：");
    	scanf("%d",&N);
    	int arr[N];
    	int sum[100];
    	int max = 1;
    	printf("请输入数组各项数值)：\n");
    	for( i = 0; i < N; i++)
    	{ 	
    		scanf("%d",&arr[i]);
    	}
    	int *p = arr;									//定义一个指针指向数组arr
    
    	for( i = 0; i < N; i++)
    	{ 
    		int s = 0;									//每次sum相加结束后。初始化为0
    		for( j = 0; j < N-i; j++)
    		{ 
    			s += *(p+i+j);							//将各项元素相加
    			sum[j] = s;
    			max = max > sum[j] ? max : sum[j];		//求最大值，赋给全局变量max
    		}	
    	}
    	printf("\n%d\n",max);							//输出最大值
    }

方法二：

#include <stdio.h>
    
    int main()
    { 	
    	int i = 0 , j = 0, N;
    	int a[20] = { 0};
    	printf("求子数组之和的最大值:\n请输入数组的项数：");
    	scanf("%d",&N);
    	printf("请输入数组各项的值：");
    	for(i = 0; i < N; i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    		
    	int max[] = { 0};
    	int sum = 0 , max_numb = 0;
    
    	for(i = 0; i < N;i++)
    	{ 
    		sum = sum + a[i];
    		if(sum < 0)
    		{ 
    			max[j] = sum - a[i];
    			max_numb = max_numb > max[j] ? max_numb : max[j];
    			j++;
    			sum = 0;
    		}
    		else
    		{ 
    			max[j] = sum;
    			max_numb = max_numb > max[j] ? max_numb : max[j];
    			j++;
    		}
    	}
    	printf("子数组之和的最大值: max_numb == %d\n",max_numb);
    	return 0;
    }

![在这里插入图片描述][20200116093810527.png]  
更多资料请点击：[我的目录][Link 1]

[Link 1]: http://note.youdao.com/noteshare?id=1370b0e8f4a16b80e7dede7836df3c08
[20200116093810527.png]: https://img-blog.csdnimg.cn/20200116093810527.png