最小子序列和__最大/最小子序列乘积

1280阅读　2评论2014-04-25　do_my_heart
分类：C/C++


点击(此处)折叠或打开

  1. 总感觉求最小子序列乘积有些问题，请高手证明下正确性

  3. /*
  4.  *最小子序列和
  5.  *最大子序列乘积
  6.  *最小子序列乘积
  7.  */

  9. #include<stdio.h>

  11. #define MAX2(A,B)    ( (A>B)?A:B )
  12. #define MIN2(A,B) ( (A>B)?B:A )

  14. int min_sub_sum(int A[],int N);
  15. int max_sub_multi(int A[],int left,int right);

  17. int min_sub_multi(int A[],int left,int right);


  20. int main(void)
  21. {
  22.     int A[] = {4,0,0,3};
  23.     
  24.     for(int i = 0; i < sizeof(A)/sizeof(int);++i)
  25.         printf("%d ",A[i]);
  26.     putchar('\n');
  27.     
  28.     printf("最小子序列和为:%d\n", min_sub_sum(A,sizeof(A)/sizeof(int)) );
  29.     printf("最大子序列乘积为:%d\n", max_sub_multi(A,0,sizeof(A)/sizeof(int)-1) );
  30.     printf("最小子序列乘积为:%d\n", min_sub_multi(A,0,sizeof(A)/sizeof(int)-1) );
  31.     
  32.     return 0;
  33. }

  35. //o(N):最小子序列的和,如果最小子序列和为正数,那么返回最小的正数
  36. int min_sub_sum(int A[],int N)
  37. {
  38.     int i,min_sum,cur_sum;
  39.     int j;
  40.     min_sum = cur_sum = 0;
  41.     j = 0;
  42.     
  43.     for(i = 0;i < N; ++i)
  44.     {
  45.         if(A[i] >= 0)
  46.             j++;
  47.         cur_sum += A[i];
  48.         if(cur_sum < min_sum)
  49.             min_sum = cur_sum;
  50.         else if(cur_sum > min_sum)
  51.             cur_sum = 0;
  52.     }
  53.     
  54.     if(j == N)
  55.     {
  56.         min_sum = A[0];
  57.         for(i = 1; i < N; ++i)
  58.         {
  59.             if(A[i] < min_sum)
  60.                 min_sum = A[i];
  61.         }
  62.     }
  63.     
  64.     return min_sum;
  65. }

  67. //o(N*logN) 最大子序列乘积
  68. int max_sub_multi(int A[],int left,int right)
  69. {
  70.     int left_max,right_max,max_from_pos,max_from_neg;
  71.     int left_max_pos,right_max_pos,left_min_neg,right_min_neg;
  72.     int multi;
  73.     int i,center;
  74.     
  75.     if(left == right)
  76.         return A[left];
  77.     
  78.     center = (left+right) / 2;
  79.     
  80.     left_max = max_sub_multi(A,left,center);
  81.     right_max = max_sub_multi(A,center+1,right);
  82.     
  83.     //分界处扩至最左边序列乘积最大正值或者最小负值
  84.     left_max_pos = left_min_neg = 0;
  85.     multi = 1;
  86.     for(i = center;i >= left; --i)
  87.     {
  88.         multi *= A[i];
  89.         if(multi > 0 && multi > left_max_pos)
  90.             left_max_pos = multi;
  91.         if(multi < 0 && multi < left_min_neg)
  92.             left_min_neg = multi;
  93.     }
  94.     
  95.     //分界处扩至最右边序列最大正值或者最小负值
  96.     right_max_pos = right_min_neg = 0;
  97.     multi = 1;
  98.     for(i = center+1 ; i <= right ; ++i)
  99.     {
  100.         multi *= A[i];
  101.         if(multi > 0 && multi > right_max_pos)
  102.             right_max_pos = multi;
  103.         if(multi < 0 && multi < right_min_neg)
  104.             right_min_neg = multi;
  105.     }
  106.     
  107.     max_from_pos = left_max_pos*right_max_pos;
  108.     max_from_neg = left_min_neg*right_min_neg;
  109.     
  110.     //找出最大值
  111.     return MAX2( MAX2(left_max,right_max) , MAX2(max_from_pos,max_from_neg) );
  112. }


  115. //o(N*logN) 最小子序列乘积
  116. int min_sub_multi(int A[],int left,int right)
  117. {
  118.     int left_min,right_min,min_from_pos,min_from_neg;
  119.     int left_max_pos,right_max_pos,left_min_neg,right_min_neg;
  120.     int multi;
  121.     int i,center;
  122.     
  123.     if(left == right)
  124.         return A[left];
  125.     
  126.     center = (left+right) / 2;
  127.     
  128.     left_min = min_sub_multi(A,left,center);
  129.     right_min = min_sub_multi(A,center+1,right);
  130.     
  131.     //分界处扩至最左边序列乘积最大正值或者最小负值
  132.     left_max_pos = left_min_neg = 0;
  133.     multi = 1;
  134.     for(i = center;i >= left; --i)
  135.     {
  136.         multi *= A[i];
  137.         if(multi > 0 && multi > left_max_pos)
  138.             left_max_pos = multi;
  139.         if(multi < 0 && multi < left_min_neg)
  140.             left_min_neg = multi;
  141.     }
  142.     
  143.     //分界处扩至最右边序列最大正值或者最小负值
  144.     right_max_pos = right_min_neg = 0;
  145.     multi = 1;
  146.     for(i = center+1 ; i <= right ; ++i)
  147.     {
  148.         multi *= A[i];
  149.         if(multi > 0 && multi > right_max_pos)
  150.             right_max_pos = multi;
  151.         if(multi < 0 && multi < right_min_neg)
  152.             right_min_neg = multi;
  153.     }
  154.     
  155.     //处理最小子序列乘积大于0时情况
  156.     if(left_min_neg == 0 && right_min_neg == 0)
  157.         return MIN2( MIN2(left_min,right_min) , MIN2(left_max_pos,right_max_pos) );
  158.     
  159.     min_from_pos = left_max_pos*right_min_neg;
  160.     min_from_neg = left_min_neg*right_max_pos;    
  161.     return MIN2( MIN2(left_min,right_min) , MIN2(min_from_pos,min_from_neg) );
  162. }


上一篇：cp命令简单实现
下一篇：没有了

文章评论