《编程珠玑》—第8章 算法设计技术

本书对《编程珠玑》第8章中分析的“最大连续子向量和”问题的3种解决方法进行了实现,并对习题中的最大矩形子数组和给出代码。

1.最大连续子向量和

问题描述:

输入是一个具有个整数的向量,输出是的任何连续子向量中的最大和。注意,当所有输入都是负数时,总和最大的子向量是空向量,总和是0。

1.1 累加数组法

  • 首先定义,所以可以得到。利用它可以得到复杂度为的代码。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include<iostream>
    #include<vector>
    using namespace std;

    //计算nums从0位置到各个位置上的累加和
    vector<int> Cumulative(const vector<int>& nums){
    int len = nums.size();
    vector<int> cum(len);
    cum[0] = nums[0];
    for(int i = 1; i < len; ++i){
    cum[i] = cum[i - 1] + nums[i];
    }
    return cum;
    }

    //连续子向量的最大和
    int maxSubArray(vector<int>& nums){
    vector<int> cumarr = Cumulative(nums);
    int maxSubSum = 0, n = nums.size();
    for(int i = 0; i < n; ++i){
    for(int j = i; j < n; ++j){
    maxSubSum = max(cumarr[j] - cumarr[i - 1], maxSubSum);
    }
    }
    return maxSubSum;
    }

    int main(){
    vector<int> nums = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    cout << maxSubArray(nums) << endl;
    return 0;
    }

1.2 分治算法

  • 这里将个元素的向量在中间分成两个长度差不超过1的子向量,分别称为

  • 递归处理这两个子向量,分别找出它们中总和最大的子向量,称为

  • 但是最终的解可能是横跨的,将这个子向量称为一定是中包含右边界的最大子向量和中包含左边界的最大子向量的组合。

  • 最终的解应该是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include<iostream>
    #include<vector>
    using namespace std;

    //分治法计算从start到end位置的连续子向量的最大和
    int maxSum(vector<int>& nums, int start, int end){
    if(start > end) return 0;
    if(start == end)
    return max(nums[start], 0);
    int mid = start + (end - start) / 2;
    //计算从mid开始向左边的最大和
    int lmax = 0, rmax = 0, sum = 0;
    for(int i = mid; i >= start; --i){
    sum += nums[i];
    lmax = max(lmax, sum);
    }
    //计算从mid+1向右边的最大和
    sum = 0;
    for(int i = mid + 1; i <= end; ++i){
    sum += nums[i];
    rmax = max(rmax, sum);
    }
    sum = lmax + rmax;
    //分治和递归
    return max(max(sum, maxSum(nums, start, mid - 1)), maxSum(nums, mid + 1, end));
    }

    int maxSubArray(vector<int>& nums){
    return maxSum(nums, 0, nums.size() - 1);
    }

    int main(){
    vector<int> nums = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    cout << maxSubArray(nums) << endl;
    return 0;
    }

1.3 扫描算法

这里尝试使用动态规划的思想去解决这个问题。

  • 假设已经解决了的问题,现在就是要扩展到包含的问题。因此最大总和子向量要么还是在中,要么变成了以结尾的新的子向量。

  • 表示结束位置为的最大子向量的和,那么对于位置来说应该有这样的迭代式。

    表示的最大子向量的和,那么对于位置来说应该有这样的迭代式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<vector>
using namespace std;

int maxSubArray(vector<int>& nums){
int maxendinghere = 0, maxsofar = 0;//以i位置结尾的最大值, 全局的最大值
for(int i = 0; i < nums.size(); ++i){
maxendinghere = max(maxendinghere + nums[i], 0);
maxsofar = max(maxsofar, maxendinghere);
}
return maxsofar;
}

int main(){
vector<int> nums = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
cout << maxSubArray(nums) << endl;
return 0;
}

2.最大矩形子数组

问题描述:

给定一个的实数数组,求出矩形子数组的最大值。

思路:

  • 这个维度上考虑各个第行到第行的矩形中的最大矩形子数组,最后选出一个最大的。

  • 在第行到第行的矩形中,将矩形压缩成一维数组(即),对这个数组使用扫描算法求出第行的矩形中的最大矩形子数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include<iostream>
    #include<vector>
    using namespace std;

    int maxSubMatrix(vector<vector<int>>& matrix){
    int m = matrix.size(), n = matrix[0].size();
    int maxMatrix = 0;
    for(int i = 0; i < m; ++i){
    vector<int> sub(n, 0);
    for(int j = i; j < m; ++j){
    int maxEndingHere = 0;
    for(int k = 0; k < n; ++k){
    sub[k] += matrix[j][k];
    maxEndingHere = max(maxEndingHere + sub[k], 0);
    maxMatrix = max(maxMatrix, maxEndingHere);
    }
    }
    }
    return maxMatrix;
    }

    int main(){
    vector<vector<int>> nums = {{-1, 2, -6, 0}, {3, 4, 5, 0},
    {1, 6, 4, 0}, {3, 8, 2, -1},
    {0, -2, 1, -1}};
    cout << maxSubMatrix(nums) << endl;
    return 0;
    }
------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》—第8章 算法设计技术

文章作者:Perry

发布时间:2019年07月25日 - 17:46

最后更新:2019年09月19日 - 13:47

原始链接:https://perry96.com/archives/aeb06325.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%