Chinaunix首页 | 论坛 | 博客
  • 博客访问: 559248
  • 博文数量: 104
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1559
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-21 00:58
个人简介

锻炼精神,首先要锻炼肉体

文章分类

全部博文(104)

文章存档

2018年(1)

2016年(1)

2015年(101)

2014年(1)

我的朋友

分类: C/C++

2015-03-01 09:59:42

题目链接:

该问题为最大子列和问题,所使用的解决方法是线性算法来解决

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. int maxSum ( int *arr , int len )
  4. {
  5.     int max , sub ;

  6.     max = sub = 0 ;

  7.     for ( int i = 0 ; i < len ; i++ )
  8.     {
  9.         sub += arr[i] ;
  10.         if ( sub > max )
  11.             max = sub ;
  12.         if ( sub < 0 )
  13.             sub = 0 ;
  14.     }
  15.         return max ;
  16. }

  17. int main ( void )
  18. {
  19.     int arr[100000] , K ;
  20.     scanf ("%d" , &K ) ;

  21.     for ( int i = 0 ; i < K ; i++ )
  22.         scanf("%d" , &arr[i]) ;
  23.     K = maxSum ( arr , K);
  24.     printf ("%d" , K) ;

  25.     system ("pause") ;
  26.     return 0 ;
  27. }
程序已经通过全部测试点

另外有一种通过递归的方法来实现的代码如下:


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>


  3. int maxOfThree ( int a , int b , int c )
  4. {
  5.     if ( a > b ) return a > c ? a : c ;
  6.     else return b > c ? b : c ;
  7. }

  8. int maxSubSum ( int *arr , int from , int to )
  9. {
  10.     if ( from == to )
  11.     {
  12.         if ( arr[from] > 0 )
  13.             return arr[from] ;
  14.         else
  15.             return 0 ;
  16.     }

  17.     int mid = (from+to) / 2 ;
  18.     int leftMax = maxSubSum ( arr , from , mid ) ;
  19.     int rightMax = maxSubSum ( arr , mid+1 , to ) ;

  20.     // left border max
  21.     int leftBorder = 0 , maxleftBorder = 0 ;

  22.     // search from center to left <--- |center|
  23.     for ( int i = mid ; i >= from ; i-- )
  24.     {
  25.         leftBorder += arr[i] ;
  26.         if ( leftBorder > maxleftBorder )
  27.             maxleftBorder = leftBorder ;
  28.     }

  29.     // right border max
  30.     int rightBorder = 0 , maxrightBorder = 0 ;
  31.     // search from center to right
  32.     for ( int j = mid+1 ; j <= mid ; j++ )
  33.     {
  34.         rightBorder += arr[j] ;
  35.         if ( rightBorder > maxrightBorder )
  36.             maxrightBorder = rightBorder ;
  37.     }

  38.     return maxOfThree (leftMax , rightMax , (maxrightBorder+maxleftBorder)) ;
  39. }

  40. int main ( void )
  41. {
  42.     int arr[10000] , K ;
  43.     scanf ("%d" , &K ) ;

  44.     for ( int i = 0 ;i < K ; i++ )
  45.     {
  46.         scanf ("%d" , &arr[i]) ;
  47.     }

  48.     K = maxSubSum(arr , 0 , K-1 ) ;


  49.     printf ("max sub sum = %d " , K ) ;
  50.     system("pause") ;
  51.     return 0 ;
  52. }

此种方法稍加改进可以得到子序列在数列中的首尾坐标,时间复杂度为 O(NlogN)
前一种方法的时间复杂度为 O(N) , 是一种在线处理算法。

如果需要求解的问题中不需要求取子序列在原数列中的起始结尾坐标的话,使用第一种方法最佳。
如果需要求解的问题需要求取子序列坐标,第一种方法无法求解,第二种实现方法最为适合。
阅读(899) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~