chapter 8

1. 内容##

本章以寻找最大连续子向量这个问题为载体，展示了怎么用多种算法设计技巧来设计更加高效的算法。

1.1 最基础的O(n^3)算法###

不写了。

1.2 两个O(n^2)算法###

一个利用arr[i...j-1] 与arr[i...j]的关系。

一个利用数组的累加，则com[j]-com[i-1]=arr[i...j]

1.3 利用分治的O(nlogn)算法###

把寻找整个数组的最大连续子向量问题分割为寻找两个字数组的最大子向量以及跨两个组的最大子向量三者中的最大，T(n)=2T(n/2)+O(n), 则最后复杂度为O(nlogn)

//
//  main.cpp
//  HelloWorld
//
//  Created by YangKi on 15/12/2.
//  Copyright (c) 2015年 YangKi. All rights reserved.
//

#include<stdio.h>
#include<string.h>
#include<assert.h>
int a[6]={3,4,-2,-9,10,8};
int max(int a, int b)
{
    return a>=b? a : b;
}

int maxsum3(int l, int u)
{
    if(l>u) return 0;
    if(l==u)return max(0, a[l]);
    int mid= (l+u)/2;
    
    int lmax=0, sum=0;
    for (int i=mid; i>=l; i--)//因为连续子向量的一个边界已经知道了，所以O(n)遍历一边就可以把最大的连续子向量找出来
    {
        sum+=a[i];
        lmax=max(lmax, sum);
    }
    
    int rmax=0;
    sum=0;
    for(int i=mid+1; i<=u; i++)
    {
        sum+=a[i];
        rmax=max(rmax, sum);
    }
    
    return max(max(maxsum3(l, mid), maxsum3(mid+1, u)), lmax+rmax);
}
int main()
{
    printf("%d\n", maxsum3(0, 5));
    return 0;
}

1.4 利用动态规划的O(n)算法###

定义一个状态数组d[],d[i－1]表示以从0->i-1这个数组范围内的以arr[i-1]这个元素为结尾的最大连续子向量的值，则很明显，max( d[0], d[1]... d[len-1])就是整个数组范围内的最大连续子向量的结果，那么假设已解决d[i-1],怎么根据d[i-1]来求d[i]呢？首先，把以arr[i]为结尾的向量分为两种，1. 只有arr[i]一个成员 2.arr[i]与前面的向量连接组成的向量。两者中的较大值就是d[i]。

//
//  main.cpp
//  HelloWorld
//
//  Created by YangKi on 15/8/31.
//  Copyright (c) 2015年 YangKi. All rights reserved.
//

#include<stdio.h>
#include<string.h>
#include<assert.h>
int a[6]={3,4,-2,-9,10,8};
int max(int a, int b)
{
    return a>=b? a : b;
}

int maxsum4(int l, int u)
{
    int d[6];
    for(int i=0; i<6; i++)
    {
        if (i==0)
        {
            d[i]=max(0, a[i]);
        }
        else
        {
            d[i]=max(d[i-1]+a[i], a[i]);
        }
    }
    int result=-1;
    for(int i=0; i<6; i++)
    {
        if (d[i]>result) {
            result=d[i];
        }
    }
    
    return result;
}
int main()
{
    printf("%d\n", maxsum4(0, 5));
    return 0;
}

2.习题##

先空着