每日一算法:求连续子数组和的最大值

0， -2， 3， 5， -1， 2 最大值为9

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,a[10] = {1,-22,-1,-99,-8,78,66,-85,100,-95};
     
    
   

    

     

    
    

     
	int sum, cur;
     
    
   

    

     

    
    

     

      	cur = a[0];
     
    
   

    

     

    
    

     

      	sum = cur;
     
    
   

    

     

    
    

     
	for (i=1; i<10; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cur = cur<0?a[i]:a[i]+cur;  //当cur<0时，丢弃cur，重置cur为当前的元素
     
    
   

    

     

    
    

     
		if (cur > sum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			sum = cur;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("连续子数组和的最大值是:%d\n", sum);
     
    
   

    

     

    
    

     

      }
     
    
  
 

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,a[10] = {1,-22,-1,-99,-8,78,66,-85,100,-95};
     
    
   

    

     

    
    

     
	int sum, cur;
     
    
   

    

     

    
    

     
	int start1 = 0,start2 = 0,end = 0;//我们用start1，start2 来记录起始位置，end 来记录终止位置。start2 相当于“工作变量”，start1 保存历史最大和连续子数组的起始位置。
     
    
   

    

     

    
    

     

      	cur = a[0];
     
    
   

    

     

    
    

     

      	sum = cur;
     
    
   

    

     

    
    

     
	for (i=1; i<10; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (cur<0)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cur = a[i];
     
    
   

    

     

    
    

     

      			start2 = i;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cur += a[i];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if (sum < cur)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			sum = cur;
     
    
   

    

     

    
    

     

      			end = i;
     
    
   

    

     

    
    

     

      			start1 = start2;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("连续子数组和的最大值是:%d\n", sum);
     
    
   

    

     

    
    

     
	printf("这个子数组是: ");
     
    
   

    

     

    
    

     
	for (i=start1; i<=end; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d ",a[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int maxSubarray(int a[], int size)
     
    
   

    

     

    
    

     

       {//出处 http://blog.csdn.net/v_JULY_v/article/details/6126406
     
    
   

    

     

    
    

     
	int sum = 0;
     
    
   

    

     

    
    

     
	int max = - (1 << 31);//整型里面最小的数
     
    
   

    

     

    
    

     
	int cur = 0;
     
    
   

    

     

    
    

     
	while (cur < size) 
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		sum += a[cur];  
     
    
   

    

     

    
    

     

      		cur++;//挨个相加
     
    
   

    

     

    
    

     
		if (sum > max) 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			max = sum;
     
    
   

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     
		else if (sum < 0) 
     
    
   

    

     

    
    

     

      		{//如果和小于0，则重置sum
     
    
   

    

     

    
    

     

      			sum = 0;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	} 
     
    
   

    

     

    
    

     
	return max;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int a[10] = {-1,-22,1,-99,8,-78,66,-85,100,-95};
     
    
   

    

     

    
    

     
	printf("连续子数组和的最大值是:%d\n", maxSubarray(a,10));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/13772505