数组之动态规划篇

问题描述：

给定一个数组，记录一串数字，可正可负，现要求出其中最大的连续子段和。

用数组a[N]记录所要求的数组，用数组dp[N]来记录连续子段和的状态

通过分析，可以知道：

当dp[i-1]>0时，无论a[i]为何值，dp[i]=a[i-1]+a[i]

当dp[i-1]<0时，也就是dp[i]记录到一个a[i-1]是负的，可以把dp[i-1]变成负的，那么dp[i-1]记录的这一段应该截掉，应为无论后面的a[K]多大，加上个负数总不可能是最大的子段和，因此将dp[i]=a[i]，重新开始记录。

#include
#define N 15
int a[N];

int subMax(int a[],int n)
{
    int dp[N],max=0,i,l=0,r=0;
    dp[0]=a[0];
    for(i=1;i
    {
        if(dp[i-1]>0)
        {
            dp[i]=dp[i-1]+a[i];//只要前面的所有数的和是正数，我就放心加，然后再与max比较
            r++;
        }
        else
        {
            dp[i]=a[i];//如果前面的和已经是负数就没必要比较啦,重新来过
            l=i;
            r=i;
        }

        if(max
            max=dp[i];
    }
    printf("%d %d\n",l,r);
    return max;
}

int main()
{
    int i;
    for(i=0;i
    {
        scanf("%d",&a[i]);
    }
    int maxSum=subMax(a,N);
    printf("the max sum: %d\n",maxSum);
    return 0;
}


/*
1 4 0 7 9 0 13 -16 -19 20 -24 0 27 28 29
12 14
the max sum: 84
Press any key to continue
*/

// 子数组的最大和
int Sum(int* a, int n)
{
    int curSum = 0;
    int maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        if (curSum + a[i] < 0)
            curSum = 0;
        else
        {
            curSum += a[i] ;
            maxSum = max(maxSum, curSum);
        }
    }
    return maxSum;
}

最大积连续子序列问题
 
给定一个整型数足a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84
分析

与最大子段和类似，注意处理负数的情况，

对于最大积问题： 
由于负数的存在，我们不能简简单单只存一个当前最大值，我们还需要存当前最小值。这里可以先把两个数的情况剪枝掉，还有用个数记录全0,如果是全0,直接返回0,OK!

#include
#define min(a,b) a
#define max(a,b) a>b? a:b
int a[100];

// 子数组的最大和，要排除全为0和 -x 0
//由于负数的存在，我们不能简简单单只存一个当前最大值，我们还需要存当前最小值。
//这里有个bug，就是如果前全都是0也会输出1
int maxProduct(int* a, int n)
{
    int maxProduct = 1; // max positive product at current position
    int minProduct = 1; // min negative product at current position
    int r = 1; // result, max multiplication totally

    for (int i = 0; i < n; i++)
    {
        if (a[i] > 0)
        {
            maxProduct=((maxProduct==0)?1:maxProduct);
            minProduct=((minProduct==0)?1:minProduct);
            maxProduct *= a[i];
            minProduct = min(minProduct * a[i], 1);
        }
        else if (a[i] == 0)//那么这段积就打回原型为1,后面不算它
        {
            maxProduct = 0;
            minProduct = 0;
            //maxProduct = 1;
            //minProduct = 1;
        }
        else // a[i] < 0
        {
            maxProduct=((maxProduct==0)?1:maxProduct);
            minProduct=((minProduct==0)?1:minProduct);
            int temp = maxProduct;
            maxProduct = max(minProduct * a[i], 1);
            minProduct = temp * a[i];
        }

        r = max(r, maxProduct);
    }

    return r;
}

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;i
    {
        scanf("%d",&a[i]);
    }
    int maxSum=maxProduct(a,n);
    printf("the maxProduct sum: %d\n",maxSum);
    return 0;
}
/*
2
0 0
the maxProduct sum: 1
Press any key to continue
2
-1 0
the maxProduct sum: 1
Press any key to continue

5
0 -1 -1 3 3
the maxProduct sum: 9
Press any key to continue


*/

最长公共子序列问题 

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

#include
#include
#define M 5
#define N 10
#define max(a,b) a>b?a:b
char A[M],B[N];
int d[M+1][N+1];
int getLCS(char *A,int m,char *B,int n)
{
    memset(d,0,sizeof(d));
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(A[i]==B[j])
            {
                d[i][j]=d[i-1][j-1]+1;
            }
            else
            {
                d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
        }
    }
    return d[M][N];
}
int main()
{

    scanf("%s",&A);
    scanf("%s",&B);
    int len=getLCS(A,M,B,N);
    printf("the lcs of A and B %d\n",len);

    return 0;
}

/*
abcdc
bffcgbffcg
the lcs of A and B 3
Press any key to continue
*/

一，    最长递增子序列问题的描述

设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=，其中k1

 以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j
如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，
把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；

如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。

dp数组记录着每个a[i]结尾的最长子序列长度，遍历一次dp 即可得到最长的子序列的长度

#include
#include
#define N 20
int a[N];
int longest(int a[],int n)
{
    int dp[N],i,t=0;
    memset(dp,0,sizeof(dp));
    dp[0]=1;

    for(i=1;i
    {
        dp[i]=1;
        for(int j=i-1;j>=0;j--)
        {
            if(a[i]>a[j] && dp[i]
                dp[i]=dp[j]+1;
        }
        if(t
            t=dp[i];
    }
    for(int k=0;k
    {
        printf("%d ",dp[k]);
    }
    printf("\n");
    return t;
}

int main()
{
    int i,n;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i
        {
            scanf("%d",&a[i]);
        }
    int maxlength=longest(a,n);
    printf("the maxlength : %d\n",maxlength);
    }
    return 0;
}
/*
10
1 4 7 2 5 8 1 9 23 1
1 2 3 2 3 4 1 5 6 1
the maxlength : 6
*/