(learn&think)

不浮躁，不自傲，学习，思考，总结

Programming Pearls: Column8

| Comments

Book notes

问题与算法

给出数组中找出连续子数组最大和。

1

直接算每个子区间的和并比较得出最大值。算法复杂度 O(n3)。 

float FindMaxSubvectorAlg1(const vector<float> &num) {
  int i, j, k;
  float sum, max_sofar;
  max_sofar = 0;
  for (i = 0; i < num.size(); ++i) {
    for (j = 0; j < num.size(); ++j) {
      sum = 0;
      for (k = i; k <= j; k++) {
        sum += num[k];
        if (sum > max_sofar) {
          max_sofar = sum;
        }
      }
    }
  }
  return max_sofar;
}

2

2.1

因为 x[i..j]直接的和可以基于 x[i..j-1]的和算出，不用重头开始算。算法复杂度 O(n2)。 

float FindMaxSubvectorAlg2(const vector<float> &num) {
  int i, j;
  float sum, max_sofar;
  max_sofar = 0;
  for (i = 0; i < num.size(); ++i) {
    sum = 0;
    for (j = i; j < num.size(); ++j) {
      sum += num[j];
      if (sum > max_sofar) {
        max_sofar = sum;
      }
    }
  }
  return max_sofar;
}
2.2

先算出 x[0..i]区间的和为 cum_vector[i] ，那么 x[i..j]区间的和就是 cum_vector[j] - cum-vector[i-1] 

float FindMaxSubvectorAlg2b(const vector<float> &num) {
  vector<float> cum_vector(num.size() + 1);
  int i, j;
  cum_vector[0] = 0;
  for (i = 1; i < cum_vector.size(); ++i) {
    cum_vector[i] = cum_vector[i - 1] + num[i];
  }
  float sum, max_sofar;
  max_sofar = 0;
  for (i = 1; i < cum_vector.size(); ++i) {
    for (j = i; j < cum_vector.size(); ++j) {
      sum = cum_vector[j] - cum_vector[i - 1];
      if (sum > max_sofar) {
        max_sofar = sum;
      }
    }
  }
  return max_sofar;
}

3

Divide-and-Conquer 算法。

  1. 求整个数组的子数组和，可以分成前面一半和后面一半
  1. 求出前半部分的最大子数组和后半部分的最大子数组和
  1. 求出两部分中间连着的子数组最大和
  1. 最后比较这 3 部分和就能得出整个个数组的子数组最大和 
float FindMaxSubvectorAlg3Core(const vector<float> &num, int l, int u) {
  if (l > u) {
    return 0;
  }
  if (l == u) {
    return max<float>(num[l], 0);
  }
  int m;
  m = (l + u) / 2;
  float lmax, rmax, sum;
  lmax = sum = 0;
  for (int i = m; i >= l; --i) {
    sum += num[i];
    if (sum > lmax) {
      lmax = sum;
    }
  }
  rmax = sum = 0;
  for (int i = m + 1; i <= u; ++i) {
    sum += num[i];
    if (sum > rmax) {
      rmax = sum;
    }
  }
  return max(lmax + rmax, max(FindMaxSubvectorAlg3Core(num, l, m),
                              FindMaxSubvectorAlg3Core(num, m + 1, u)));
}

float FindMaxSubvectorAlg3(const vector<float> &num) {
  return FindMaxSubvectorAlg3Core(num, 0, num.size() - 1);
}

4

假定已经解决了 x[0..i-1]的情况，那么如何扩展到 x[0..i]的情况，只多了 x[i] 元素？

  1. 解决了 x[0..i-1]的情况，有这区间的最大子数组和 max_sofar ，和必须以 x[i-1]结尾的子数组最大和;
  2. 到 x[0..i]的情况，就要把必须以 x[i-1]结尾的子数组最大和与 x[i]相加，如果以 x[i-1]结尾的子数组为负数的话，加了反而减少总和。所以此种情况以 x[i]的和就是 x[i];
  3. 最后把以 x[i]与在区间 x[0..i-1]的最大子数组和 max_sofar 比较，就能解决 x[0..i]的情况;
  4. 如此一直扩展到 x[0..n]算出整个数组的最大子数组和。

只扫描一遍，算法复杂度 O(n)。 

float FindMaxSubvectorAlg4(const vector<float> &num) {
  float max_sofar, max_ending_here;
  max_sofar = max_ending_here = 0;
  for (int i = 0; i < num.size(); ++i) {
    max_ending_here += num[i];
    if (max_ending_here < 0) {
      max_ending_here = 0;
    }
    if (max_ending_here > max_sofar) {
      max_sofar = max_ending_here;
    }
  }
  return max_sofar;
}

算法设计技巧

  • 保存状态防止重复计算。
  • 预处理信息到适当的数据结构中来加快之后的计算。比如先建立堆，先排序等。
  • 分而治之，把大问题分成类似的小问题解决。
  • 扫描算法。比如解出了 x[0..i-1]如何扩展到 x[0..i].
  • 累积。
  • 确定问题的算法复杂度下界。

Problems

10

  1. 初始化累积和数组 cum，使得 cum[i]=x[0]+x[1]...x[i] ， 那么要 x[l..u] 区间的和为 0 的话，cum[l-1] = cum[u]
  2. 排序 cum 数组;
  3. 扫描排序好的数组 cum，找出最相近的相邻数组元素即得到结果。

算法复杂度 O(n) + O(nlogn) + O(n-1) = O(nlogn).

找出子数组和与一个特定值 r 最相近，算法类似，只是 step3 找出与 r 最相近的相邻数组元素。

11

  1. 累积收费和数组 cum，使得 cum[i]=x[0]+x[1]...x[i]
  2. 计算 l 和 u 关卡之间的收费 cum[u]-cum[l]

Comments