一、求局部最大值

1. 题目

给定一个无重复元素的数组 A[0…N-1]，求找到一个该数组的局部最大值。规定：在数组边界外的值无穷小。即：A[0]>A[-1]，A[N-1] >A[N]。

显然，遍历一遍可以找到全局最大值，而全局最大值显然是局部最大值，时间复杂度为 O(N)。

可否有更快的办法？

2. 分析

首先给出“高原数组”定义（邹博老师自创的）。

定义：若子数组 Array[from,…,to] 满足

• Array[from]>Array[from-1]
• Array[to]>Array[to+1]

称该子数组为“高原数组”。

例如对于数组 3,5,1,2,6,7,14，因为 2 <6，14>4，可以认为 6,7,14 就是其中的一个高原数组。
用图像形象地表示为：

若高原数组长度为 1，则该高原数组的元素为局部最大值。

因此寻找局部最小值的算法就变成了寻找长度为 1 的高原数组。
（这里特别注意！题中只要求找到一个局部最大值即可！）

算法描述：
使用索引 left、right 分别指向数组首尾，根据定义，该数组为高原数组。

• 求中点 mid=(left+right)/2
• A[mid]>A[mid+1]，子数组 A[left…mid] 为高原数组
• 丢弃后半段：right=mid
• A[mid+1]>A[mid]，子数组 A[mid…right] 高原数组
• 丢弃前半段：left=mid+1
• 递归直至 left==right

该算法的时间复杂度为 O(logN)，最重要的是给了我们一些思维上的启发，即特别大的数据，我并不需要完全遍历一遍，就能知道这个数据中的某些有效的局部特征。

3. 代码

/**
 * 寻找一个局部最小值
 */
int local_maximum(const int* a, int n){
    int left = 0;
    int right = n - 1;
    int mid;
    while(left < right){mid = (right - left) / 2 + left; 
        // 防溢出，等价于 mid = (left + right) / 2 
        cout<<a[mid]<<endl;
        if(a[mid] > a[mid+1])
            right = mid;
        else
            left = mid + 1;
    }
    return a[left];
}

二、子集和数问题

1. 题目

已知数组 A[0…N-1]，给定某数值 sum，找出数组中的若干个数（可以为 0 个或 n 个），使得这些数的和为 sum。
（假定数组中的元素都大于 0：A[i]>0）

例如,
对于数组 1,2,3,4,5，给定 sum=10，则满足条件的若干个数有：
1, 2, 3, 4
1, 4, 5
2, 3, 5

2. 分析与代码

显然，这个问题是一个 NP 完全问题。

针对此题，可以设置布尔向量 x[0…N-1]（标记数组）来表示取了哪个元素，x[i]= 0 表示不取 A[i]，x[i]= 1 表示取 A[i]，与 0 - 1 背包问题的设置方法类似。

(1). DFS 递归遍历

首先上场的是 DFS 递归遍历，利用函数的参数 i 表示当前进行到的位置，用 has 表示已经加入的元素当前的和，代码如下：

int a[] = {1,2,3,4,5};
int n = sizeof(a) / sizeof(int);
int sum = 10;

/**
 * 直接递归
 * x[] 为最终解，i 为考察 a[i] 是否加入，has 表示当前的和
 */
void enum_sum_number(bool *x, int i, int has){if(i>=n) return;
    if(has + a[i] == sum){x[i] = true;
        print(a,x); // 自定义的输出函数
        x[i] = false;
    }
    x[i] = true;
    enum_sum_number(x, i + 1, has + a[i]);
    x[i] = false;
    enum_sum_number(x, i + 1, has);
}

(2). 分支限界法

然后考虑对 DFS 进行优化，便有了分支限界法。
考虑如何对分支进行限界，前提：数组 A[0…N-1] 的元素都大于 0。
考察向量 x[0…N-1]，假定已经确定了前 i 个值，现在要判定第 i + 1 个值 x[i] 为 0 还是 1。
假定由 x[0…i-1] 确定的 A[0…i-1] 的和为 has；A[i,i+1,…N-1] 的和为 residue(简记为 r)；

• has + a[i] ≤ sum 并且 has + r ≥ sum：x[i] 可以为 1；
• has + (r - a[i]) >= sum：x[i] 可以为 0；

（注意，在编写代码进入分支的时候，要注意避免重复进入分支！）

代码如下：

/**
 * 分支限界
 */
void enum_sum_number2(bool *x, int i, int has, int residue){if(i>=n) return;
    if(has + a[i] == sum){x[i] = true;
        print(a,x);
        x[i] = false;
    } else if(has + residue >= sum && has + a[i] <= sum){// 注意此处是 else if，因为若进入了 has + a[i] == sum 分支，// 意味着已经选了 a[i] 了，所以此处不需要重复选择 a[i] 了
        x[i] = true;
        enum_sum_number2(x, i + 1, has + a[i], residue - a[i]);
    }
    if(has + residue - a[i] >= sum){x[i] = false;
        enum_sum_number2(x, i + 1, has, residue - a[i]);
    }
}

数理逻辑的重要应用：分支限界的条件

思考：

• 分支限界的条件是充分条件吗？（不是，是必要条件）
• 在新题目中，如何发现分支限界的条件。

（学会该方法，比此问题本身更重要）

(3). 考虑负数的情况

给出一个例子：数组 -3,-5,-2,4,2,1,3，给定 sum = 5，
符合要求的数有
-3, -2, 4, 2, 1, 3
-3, 4, 1, 3
-5, 4, 2, 1, 3
-2, 4, 2, 1
-2, 4, 3
4, 1
2, 3

DFS 因为是枚举，肯定能够得到正确解，关键是如何对负数的情况进行分支限界？

下面给出一种方法：

可对整个数组 A[0…N-1] 进行正负排序，使得负数都在前面，正数都在后面（只需要保证负数部分在前面即可，不需要保证负数部分内部也是有序的），使用剩余正数的和作为分支限界的约束：

• 如果 A[i] 为负数：如果全部正数都算上还不够，就不能选 A[i]；
• 如果递归进入了正数范围，按照数组是全正数的情况正常处理；

代码如下：

/**
 * 一种正负排序的实现，并计算 negative 和 positive
 */
void positive_negative_sort(int a[], int n, int &negative, int &positive){
    int k = 0;
    negative = positive = 0;
    for(int i=0; i<n; i++)
        if(a[i] < 0){negative += a[i];
            swap(a[i], a[k]);
            ++k;
        } else
            positive += a[i];
}

/**
 * 含有负数的分支限界
 */
void enum_sum_number3(bool x[], int i, int has, int negative, int positive){if(i >= n) return;
    if(has + a[i] == sum){x[i] = true;
        print(a,x);
        x[i] = false;
    } 
    if(a[i] > 0){
        // 正数的情况
        if(has + positive >= sum && has + a[i] <= sum){x[i] = true;
            enum_sum_number3(x, i + 1, has + a[i], negative, positive - a[i]);
            x[i] = false;
        }
        if(has + positive - a[i] >= sum){x[i] = false;
            enum_sum_number3(x, i + 1, has, negative, positive - a[i]);
        }
    } else {
        // 负数的情况
        if(has + x[i] + positive >= sum){x[i] = true;
            enum_sum_number3(x, i + 1, has + a[i], negative - a[i], positive);
            x[i] = false;
        }
        if(has + negative <= sum && has + positive >= sum){x[i] = false;
            enum_sum_number3(x, i + 1, has, negative - a[i], positive);
        }
    }
}