数组分段和最大值最小问题

1. 题目：给定一个数组，和一个值k，数组分成k段。要求这k段子段和最大值最小。求出这个值。

2.分析：这道题目很经典，也很难，个人认为很难。文章中给出了三种算法：算法1，暴力搜索。本题暴力搜索算法并不是很明显，可以使用递归实现暴力搜索。递归首先要有递归式：

                 n                             n-1
M[n, k] = min { max { M[j, k-1], ∑ A_i } }
                j=1                            i=j

n表示数组长度，k表示数组分成几段。初始化条件：

M[1, k] = A0

          n-1
M[n, 1] = ∑ Ai
i=0
很容易发现上述的递归算法拥有指数时间的复杂度，并且会重复计算一些M值。这类的算法一般可以使用动态规划进行优化。使用数组保存一些已经计算得到
的值，采用从低向上进行计算。这就是算法2。文章中还给出了第三种很牛的算法，我是想不到的。这就是使用二分查找应用到这个题目。大牛真是太牛了！！ 下面是代码：

#include <iostream>
#include <cassert>

using namespace std;
int sum(int A[], int from, int to) { 
    int total = 0; 
    for (int i = from; i <= to; i++) 
        total += A[i]; 
    return total; 
} 
//递归的暴力搜素算法
//指数时间的复杂度
int partition(int A[], int n, int k) { 
    if (k == 1) 
        return sum(A, 0, n-1); 
    if (n == 1) 
        return A[0]; 

    int best = INT_MAX; 
    for (int j = 1; j <= n; j++) 
        best = min(best, max(partition(A, j, k-1), sum(A, j, n-1))); 

    return best; 
}

//改进的动态规划算法
//时间复杂度：O(kN2)
//空间复杂度：O(kN) 
const int MAX_N = 100; 
int findMax(int A[], int n, int k) { 
    int M[MAX_N+1][MAX_N+1] = {0}; 
    int cum[MAX_N+1] = {0}; 
    for (int i = 1; i <= n; i++) 
        cum[i] = cum[i-1] + A[i-1]; 

    for (int i = 1; i <= n; i++) 
        M[i][1] = cum[i]; 
    for (int i = 1; i <= k; i++) 
        M[1][i] = A[0]; 

    for (int i = 2; i <= k; i++) { 
        for (int j = 2; j <= n; j++) { 
            int best = INT_MAX; 
            for (int p = 1; p <= j; p++) { 
                best = min(best, max(M[p][i-1], cum[j]-cum[p])); 
            } 
            M[j][i] = best; 
        } 
    } 
    return M[n][k]; 
}


int getMax(int A[], int n) { 
    int max = INT_MIN; 
    for (int i = 0; i < n; i++) { 
        if (A[i] > max) max = A[i]; 
    } 
    return max; 
} 

int getSum(int A[], int n) { 
    int total = 0; 
    for (int i = 0; i < n; i++) 
        total += A[i]; 
    return total; 
} 

int getRequiredPainters(int A[], int n, int maxLengthPerPainter) { 
    int total = 0, numPainters = 1; 
    for (int i = 0; i < n; i++) { 
        total += A[i]; 
        if (total > maxLengthPerPainter) { 
            total = A[i]; 
            numPainters++; 
        } 
    } 
    return numPainters; 
} 


//想不到的二分查找算法
//时间复杂度：O(N log ( ∑ Ai )).
//空间复杂度：0(1)
int BinarySearch(int A[], int n, int k) { 
    int lo = getMax(A, n); 
    int hi = getSum(A, n); 

    while (lo < hi) { 
        int mid = lo + (hi-lo)/2; 
        int requiredPainters = getRequiredPainters(A, n, mid); 
        if (requiredPainters <= k) 
            hi = mid; 
        else
            lo = mid+1; 
    } 
    return lo; 
}
int main()
{
    enum{length=9};
    int k=3;
    int a[length]={9,4,5,12,3,5,8,11,0};
    cout<<partition(a,length,k)<<endl;
    cout<<findMax(a,length,k)<<endl;
    cout<<BinarySearch(a,length,k)<<endl;
    return 0;
}

参考文章：

http://www.leetcode.com/2011/04/the-painters-partition-problem-part-ii.html

http://www.leetcode.com/2011/04/the-painters-partition-problem.html