コラム8

『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』のコラム8は「アルゴリズムデザインのテクニック」です。
その中で，以下のような問題がありました。

今，n要素の浮動小数点数の配列xを入力とし，配列xの連続した要素(部分配列)でその和が最大になるものを見つけ，その和を出力します。

この問題に対して，, , ，というふうに実行速度を上げていく過程が興味深いです。以下の関数maxsum3は，分割統治法を使ってにしているのですが，更に関数maxsum4では，まで持っていっています。

#include <stdio.h>

#define SIZE 10
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxsum1(int *x, int l, int u); /* O(n^3)のアルゴリズム */
int maxsum2(int *x, int l, int u); /* O(n^2)のアルゴリズム */
int maxsum3(int *x, int l, int u); /* O(nlog(n))のアルゴリズム */
int maxsum4(int *x, int l, int u); /* O(n)のアルゴリズム */

int maxsum1(int *x, int l, int u)
{
  int i, j, k, sum, maxsofar = 0;
  for (i = l; i < u; i++) {
    for (j = i; j < u; j++) {
      sum = 0;
      for (k = i; k <= j; k++) {
        sum += x[k];
      }
      maxsofar = MAX(maxsofar, sum);
    }
  }
  return maxsofar;
}

int maxsum2(int *x, int l, int u)
{
  int i, j, sum, maxsofar = 0;
  for (i = 0; i < u; i++) {
    sum = 0;
    for (j = i; j < u; j++) {
      sum += x[j];
      maxsofar = MAX(maxsofar, sum);
    }
  }
  return maxsofar;
}

int maxsum3(int *x, int l, int u)
{
  int i, m, sum, lmax, rmax;
  if (l > u) return 0;
  if (l == u) return MAX(0, x[l]);
  m = (l + u) / 2;
  lmax = sum = 0;
  for (i = m; i >= l; i--) {
    sum += x[i];
    lmax = MAX(lmax, sum);
  }
  rmax = sum = 0;
  for (i = m + 1; i <= u; i++) {
    sum += x[i];
    rmax = MAX(rmax, sum);
  }
  return MAX(lmax + rmax, MAX(maxsum3(x, l, m), maxsum3(x, m + 1, u)));
}

int maxsum4(int *x, int l, int u)
{
  int i, maxsofar = 0, maxendinghere = 0;
  for (i = l; i < u; i++) {
    maxendinghere = MAX(maxendinghere + x[i], 0);
    maxsofar = MAX(maxsofar, maxendinghere);
  }
  return maxsofar;
}

int main(void)
{
  int data[SIZE] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};

  printf("maxsum1 = %d\n", maxsum1(data, 0, SIZE - 1));
  printf("maxsum2 = %d\n", maxsum2(data, 0, SIZE - 1));
  printf("maxsum3 = %d\n", maxsum3(data, 0, SIZE - 1));
  printf("maxsum4 = %d\n", maxsum4(data, 0, SIZE - 1));

  return 0;
}

追記(2008/12/08)

上記のプログラムで，MAXというマクロを使っていますが，関数maxsum3において，このマクロを使用するのは最悪でした…(コラム9問題2参照)。p122の問題4はこの件に関する面白い問題です。
マクロを使った場合，使わない場合でarrmax関数が呼ばれた回数を数えてみました。

#include <stdio.h>

#define SIZE 10
#ifdef USE_MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#endif

int arrmax(int *x, int n);
#ifndef USE_MAX
int max(int a, int b);
#endif
static int counter = 0;         /* arrmax関数が呼ばれた回数 */

int arrmax(int *x, int n)
{
  counter++;
  if (n == 1)
    return x[0];
  else
#ifdef USE_MAX
    return MAX(x[n - 1], arrmax(x, n - 1));
#else
  return max(x[n - 1], arrmax(x, n - 1));
#endif
}

#ifndef USE_MAX
int max(int a, int b) 
{
  return a > b ? a : b;
}
#endif

int main(void)
{
  int data[SIZE] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

  printf("Max = %d\n", arrmax(data, SIZE));
  printf("count = %d\n", counter);
  return 0;
}

以下が実行結果です。

• 関数maxを使った場合，arrmax関数は10回呼ばれています。

Max = 10
count = 10

• マクロMAXを使った場合，arrmax関数は，なんと1023回呼ばれています…。

Max = 10
count = 1023