Pearls8

问题

输入具有n个浮点数的向量x,输出是输入向量的任意连续子向量的最大和。

8.2 .两个平方算法

int maxSum1(int arr[],int sz)
{
    int i,j,maxsofar,sum;
    maxsofar = 0;
    sum = 0;
    for(i = 0;i < sz;i++)
    {
        sum = 0;
        for(j = i ;j < sz;j++)
        {
            sum = sum + arr[j];
            maxsofar = max(sum,maxsofar);
        }
    }
    return maxsofar;
}
//n*n
int maxSum2(int arr[],int sz)
{
    int i,j,maxsofar,sum;
    int *arraux = (int*)malloc (sizeof(int) * (sz + 1));
    arraux[0] = 0;
    for(i = 1;i <= sz;i++)
    {
        arraux[i] = arraux[i-1] + arr[i - 1];
    }
    maxsofar = 0;
    for(i = 1;i <= sz;i++)
    {
        for(j = i ;j <= sz;j++)
        {
            sum = arraux[j] - arraux[i - 1];
            maxsofar = max(sum,maxsofar);
        }
    }
    return maxsofar;
}

8.3 .分治算法

//n*log n
int maxSum3(int arr[],int sz,int lo,int up)
{
    if(lo > up) return 0;
    if(lo == up) return max(0,arr[lo]);
    int m = lo + (up - lo) / 2;
    int lmax,sum,rmax,i;
    lmax = sum = 0;
    for(i = m;i >= lo ; i--)
    {
        sum += arr[i];
        lmax = max(lmax,sum);
    }
    rmax = sum = 0;
    for(i = m + 1;i <= up; i++)
    {
        sum += arr[i];
        rmax = max(rmax,sum);
    }
    return max(lmax+rmax,max(maxSum3(arr,sz,lo,m),maxSum3(arr,sz,m+1,up))); 
}

8.4 .扫描算法

int maxSum4(int arr[],int sz)
{
    int maxsofar = 0,maxendinghere = 0 ,i;
    for(i = 0;i < sz;i++)
    {
        maxendinghere = max(maxendinghere+arr[i],0);
        maxsofar = max(maxsofar,maxendinghere);
    }
    return maxsofar;
}

测试程序

//#define LOCAL
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int maxn=50001;
int num[maxn],N;
int cnt=0;
void Init()
{
    cin >> N; 
    for(int i = 0;i < N;i++)
    {
        cin >> num[i];
    }
}
int main(void)
{
#ifndef LOCAL
    freopen("1049.in","r",stdin);
    freopen("1049.out","w",stdout);
#endif
    Init();
    cout << maxSum1(num,N) << endl;
    cout << maxSum2(num,N) << endl;
    cout << maxSum3(num,N,0,N) << endl;
    cout << maxSum4(num,N) << endl;
    return 0;
}