[C Programming] 等值首尾和-延伸

1. 這個程式要求所有元素都大於零，是否有此必要？
    如果沒有這個條件，請證明它；如果不行，請改寫程式。
2. 請改寫程式，將造成前段和與後段和相同的指標，
    連同這個相等的值一併顯示出來。

個人解法：
1. 很明顯有必要，因為原本的寫法是假設：
  「往下多加一個元素會得到更大的前段/後段和」。
    如果元素是負的，甚至可能會令前段或後段和等同於更之前已經碰到過的前後段和。
    不說其他，就算只限制不小於零，也可能造成平台的問題。
    比如2,3,0,0,3,2，兩個零的部分會造成4種組合。
    改寫程式的話，可能就要比較全體的和了。
    可以藉由迴圈不斷將上一個加總到下一個去，免去從f[]的開頭加到後面，
    這也是一種空間換取時間的做法。
    經過sorting的話，可以利用之前做的等值數目延伸問題的code，
    來計算確切的組數。
    由於出去之後並沒有回傳pointer，所以多花點功夫作free的動作，
    算是養成好習慣吧XD
 
Code部分如下:

int headtail_neg(int f[], int n)
{
 int* presum = (int*)malloc(sizeof(int)*n);
 int* sufsum = (int*)malloc(sizeof(int)*n);
 int pre = 0, count = 0;
 presum[0] = f[pre]; sufsum[0] = f[n-1];
 // Calculate each prefix-sum and suffix-sum.
 for(pre = 1; pre < n; pre++)
 {
  presum[pre] = f[pre] + presum[pre-1];
  sufsum[pre] = f[n-1-pre] + sufsum[pre-1];
 }
 qsort(presum, n, sizeof(int), sort);
 qsort(sufsum, n, sizeof(int), sort);
 
 count = eq_cnt(presum, sufsum, n, n); // 見等值數目-延伸
 free(presum); presum = 0;
 free(sufsum); sufsum = 0;
 return count;
}

2. 只要在搜尋到的時候輸出printf就可以了。

在原程式中count++底下加入該行：

printf("\nCount: %2d (prefix,suffix):(%2d,%2d) sum = %2d",count,pre,suf,presum);

範例輸出結果:

Count:  1 (prefix,suffix):( 0,10) sum =  0
Count:  2 (prefix,suffix):( 1, 9) sum =  1
Count:  3 (prefix,suffix):( 2, 8) sum =  3
Count:  4 (prefix,suffix):( 3, 7) sum =  6
Count:  5 (prefix,suffix):( 4, 6) sum = 11
Count:  6 (prefix,suffix):( 5, 5) sum = 18
Count:  7 (prefix,suffix):( 6, 4) sum = 26
Count:  8 (prefix,suffix):( 7, 3) sum = 33
Count:  9 (prefix,suffix):( 8, 2) sum = 38
Count: 10 (prefix,suffix):( 9, 1) sum = 41
Count: 11 (prefix,suffix):(10, 0) sum = 43
Total Count: 11