I. Finding the Local Maximum

1. Topics

Given an array of non-repetitive elements A[0... N-1], find a local maximum of the array. Provision: Outside the boundaries of the array, the value is infinitesimal. Namely: A[0] > A[-1], A[N-1] > A[N].

Obviously, the global maximum can be found by traversing once, while the global maximum is obviously the local maximum, and the time complexity is O(N).

Can there be a quicker way?

2. Analysis

Firstly, the definition of "plateau array" is given (created by Professor Zou Bo).

Definition: If the subarray Array[from,... to] Satisfy

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

The subarray is called "plateau array".

For example, for arrays 3, 5, 1, 2, 6, 7, 14, because 2 < 6, 14 > 4, it can be considered that 6, 7, 14 is one of the plateau arrays.
Image representation is as follows:

If the length of the plateau array is 1, then the element of the plateau array is the local maximum.

So the algorithm for finding the local minimum becomes a plateau array of length 1.
(Special attention here! Just find a local maximum in the question!

Algorithmic description:
The index left and right are used to point to the beginning and end of the array respectively. By definition, the array is a plateau array.

• Find mid=(left+right)/2
• A[mid] > A[mid+1], sub-array A[left... Mid] is a plateau array
• Discard the second half: right=mid
• A[mid+1] > A[mid], subarray A[mid... right] plateau array
• Discard the first half: left=mid+1
• Recursion until left==right

The time complexity of the algorithm is O(logN). The most important thing is to give us some inspiration, that is, the very large data. I don't need to go through it completely to know some effective local features in this data.

3. Code

/**
 * Finding a Local Minimum
 */
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; 
        // Anti-spillover, equivalent to mid = (left + right) / 2 
        cout<<a[mid]<<endl;
        if(a[mid] > a[mid+1])
            right = mid;
        else
            left = mid + 1;
    }
    return a[left];
}

II. SUBSETS AND NUMBER PROBLEMS

1. Topics

Known array A[0... N-1]. Given a numerical sum, find a number of numbers in an array (0 or n) so that the sum of these numbers is sum.
(Assuming that all elements in an array are greater than 0:A[i]>0)

For example,
For arrays 1, 2, 3, 4, 5, given sum=10, several numbers satisfying the conditions are:
1, 2, 3, 4
1, 4, 5
2, 3, 5

2. Analysis and Code

Obviously, this problem is NP-complete.

To solve this problem, Boolean vector x[0... N-1] (tag array) denotes which element is taken, x[i]=0 denotes not taking A[i], and x[i]=1 denotes taking A[i], similar to the setting method of 0-1 knapsack problem.

(1). DFS recursive traversal

Firstly, the DFS recursive traversal is used to show the current position by the parameter i of the function and the current sum of the elements that have been added by has. The code is as follows:

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

/**
 * Direct Recursion
 * x[]For the final solution, I is to check whether a[i] is added. has denotes the current sum.
 */
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); // Custom Output Function
        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) Branch and Bound Method

Then considering the optimization of DFS, there is a branch-and-bound method.
Consider how to bound the branch, premise: Array A[0... The elements of N-1 are all greater than 0.
Consider vector x[0... N-1], assuming that the first I value has been determined, it is time to decide whether the value x[i] of the first i+1 is 0 or 1.
Suppose x[0... i-1] A[0... The sum of i-1 is has; A[i,i+1,... The sum of N-1 is residue (r).

• has + a[i] < sum and has + r (> sum: x[i] can be 1;
• Has + (r - a [i]) >= sum: x[i] can be 0;

(Note that when writing code to branch, be careful not to repeat the branch!)

The code is as follows:

/**
 * branch-and-bound
 */
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){
        // Note that this is else if, because if you enter the has + a [i]== sum branch,
        // This means that a[i] has been selected, so there is no need to repeat a[i] here.
        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]);
    }
}

An Important Application of Mathematical Logic: Conditions of Branch and Bound

Reflection:

• Is the condition of branch and bound sufficient? (No, it's a prerequisite)
• In the new topic, how to find the conditions of branch and bound.

(Learning this method is more important than the problem itself.)

(3) Consider the case of negative numbers

Given an example: array - 3, - 5, - 2, 4, 2, 1, 3, given sum = 5,
The number that meets the requirements is
-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

Because DFS is an enumeration, it must be able to get the correct solution. The key is how to branch and bound the negative number.

Here is a method:

For the whole array A[0... N-1] Orders the positive and negative numbers so that the negative numbers are in the front and the positive numbers are in the back (just make sure that the negative numbers are in the front, and do not need to ensure that the negative numbers are orderly in the interior). Use the sum of the remaining positive numbers as the constraint of the branch and bound:

• If A[i] is negative: if all positive numbers are not enough, then A[i] cannot be selected.
• If the recursion enters the positive range, it will be processed according to the case that the array is all positive.

The code is as follows:

/**
 * An Implementation of positive and negative Sorting and Calculating negative and 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];
}

/**
 * Branch and Bound with Negative Number
 */
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){
        // The case of positive numbers
        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 {
        // The case of negative numbers
        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);
        }
    }
}