以下来自小百合http://bbs.nju.edu.cn

 

现在市场上的tt大概有三类：橡胶材质的、羊肠内组织（“表皮”）材质的和聚亚安酯材
质的。不过，其中由动物表皮制成的tt允许爱滋病毒、疱疹、肝炎病原体等通过，不能称
为“安全套”；而聚亚安酯制成的更薄，更有感觉，触感比橡胶材质的好很多，不过是比
较贵哦！

 

问题：已知一个整数数组A，求一个最小的正整数M，使得M等于数组A的一个子序列的和。

 

 

设数组A的长度为n，令数组sum[1..n]为以下值：

sum[1] = A[1];

sum[2] = A[1] + A[2] = sum[1] + A[2];

......

sum[i]  = A[1] + A[2] + ... + A[i] = sum[i-1] + A[i];

......

sum[n] = A[1] + A[2] + ... + A[n] = sum[n-1] + A[n];

 

这一步的时间复杂度为O(n)。

 

 

对数组sum[1..n]进行快速排序，使该数组按升序排列。

如果sum[a] == sum[b]， 按以下规则排序：

如果 a < b，则 sum[b] 排在 sum[a] 前面。反之，sum[a] 排在 sum[b] 前面。

 

这一步的时间复杂度为O(nlogn)。

 

 

设排序后的sum数组为：

sum[a1], sum[a2], ...... sum[an]

 

按如下方式遍历该数组：

    i = [1..n]。

1) 如果 sum[ai] > 0 并且 sum[ai] < min， 令 min = sum[ai]。

2) 如果 0 < sum[a(i+1)] - sum[ai] < min 并且 a(i+1) > ai，令 min = sum[a(i+1)] - sum[ai]。

 

注意边界情况。

最后求得的min为该问题的解。

 

这一步的时间复杂度为O(n)。

 

该算法总的时间复杂度为O(nlogn)。

 

 

struct subsum
{
   int value;
   int length;
};

int minsubsum(int A[], int length)
{
   int i;
   int min = 0;

   struct subsum *sum = new struct subsum[length+1];

   sum[0].value = 0;
   sum[0].length = length+1;

   for(i=1; i<=length; i++)
   {
       sum[i].value = sum[i-1].value + A[i-1];
       sum[i].length = i;
   }

   qsort(sum+1, length, sizeof(struct subsum), compare);

   for(i=1; i<=length; i++)
   {
       if (sum[i].value > 0)
       {
           if (min == 0)
               min = sum[i].value;
           else if (sum[i].value < min)
               min = sum[i].value;
       }

  
       if (sum[i].value != sum[i-1].value && sum[i].length > sum[i-1].length)
       {
           if (min == 0)
               min = sum[i].value - sum[i-1].value;
           else if (sum[i].value-sum[i-1].value < min)
               min = sum[i].value - sum[i-1].value;
       }
   }

   delete [] sum;
   return min;
}

int compare(const void *a, const void *b)
{
    if (((struct subsum*)a)->value == ((struct subsum*)b)->value)
         return ((struct subsum*)b)->length - ((struct subsum*)a)->length;
    else
         return ((struct subsum*)a)->value - ((struct subsum*)b)->value;
}