#include <stdlib.h>
#include <stdio.h>
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  maxsubsum
 *  Description:  用分治法找出数组中的最长公共子序列
 * =====================================================================================
 */

int max3(int a, int b, int c)
{
    int max;
    if (a > b) {
        max = a;
    } else {
        max = b;
    }
    return max > c ? max : c;
}
int maxsubsum(const int a[], int left, int right)
{
    int maxleft, maxright;                      /* 左右最大子序列和 */
    int maxleftborder = 0, maxrightborder = 0;  /* 包含中间元素的左右两部份的和 */
    int leftbordersum = 0;
    int rightbordersum = 0;
    int mid, i;

    if (left == right) {
        if (a[left] > 0) {
            return left;
        } else {
            return 0;
        }
    }

    mid = (left + right) / 2;
    maxleft = maxsubsum(a, left, mid);
    maxright = maxsubsum(a, mid + 1 , right);

    for ( i = mid; i >= left; i--) {
        leftbordersum += a[i];
        if (leftbordersum > maxleftborder) {
            maxleftborder = leftbordersum;
        }
    }
    for ( i = mid + 1; i <= right; i++) {
        rightbordersum += a[i];
        if (rightbordersum > maxrightborder) {
            maxrightborder = rightbordersum;
        }
    }

    return max3(maxleft, maxright, maxleftborder + maxrightborder);
}

int main(void)
{
    int a[] = {4, -3, 5, -2, -1, 2, 6, -2};
    printf("%d\n", maxsubsum(a, 0, 7));
    return 0;
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  maxsubmulti
 *  Description:  采用分治法求解最大子序列乘积。
 *  因为负负得正，所以设置了 minleftborder,minrightborder
 * =====================================================================================
 */
#include <stdio.h>
double max4(double, double, double, double);
double maxone(const double [], int);            /* 如果maxsubmulti返回结果为1.0，则可能是都为小于1的小数且至多有一个负元素 */
double maxsubmulti(const double [], int, int);

double maxsub(const double a[], int n)
{
    double maxsubm = maxsubmulti(a, 0, n-1);
    if (maxsubm == 1.0)
        return (maxone(a, n));
    else
        return maxsubm;
}
double maxsubmulti(const double a[], int left, int right)
{
    double maxleft, maxright;
    double maxleftborder = 1, maxrightborder = 1;
    double minleftborder = 1, minrightborder = 1;
    double leftborder = 1, rightborder =1;
    int mid, i;

    if (left == right) {
        if (a[left] > 0)
            return a[left];
        else
            return 0;
    }

    mid = (left + right) / 2;
    maxleft = maxsubmulti(a, left, mid);
    maxright = maxsubmulti(a, mid + 1, right);

    for (i = mid; i >= left; i--) {
        leftborder *= a[i];
        if (leftborder > maxleftborder)
            maxleftborder = leftborder;
        if (leftborder < minleftborder)
            minleftborder = leftborder;
    }

    for (i = mid + 1; i <= right; i++) {
        rightborder *= a[i];
        if (rightborder > maxrightborder)
            maxrightborder = rightborder;
        if (rightborder < minrightborder)
            minrightborder = rightborder;
    }

    return max4(maxleft, maxright, maxleftborder * maxrightborder, minleftborder * minrightborder);
}

int main(void)
{
    double arr[6] = {-1.0, 1000.0, 0.001, 1.5, -80, 10};
    printf("%f\n",maxsub(arr, 6));
    double arb[6] = {-3, 0.02, 0.001, 0.3, 0.11, 0.210};
    printf("%f\n",maxsub(arb, 6));
    return 0;
}

double max4(double a, double b, double c, double d)
{
    double max = a;
    if (max < b)
        max = b;
    
    if (max < c)
        max = c;
    if (max < d)
        max = d;
    return max;
}

double maxone(const double a[], int n)
{
    double maxd = a[0];
    int i;
    for (i = 1; i < n; i++)
        if (a[i] > maxd)
            maxd = a[i];
    return maxd;
}

#include <stdio.h>
#include <stdlib.h>
 
// max1num返回数组中最大值
int max1num(int a[], int n)
{
    int i,max;
    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}
 
//求数组a的最大子序列和
int maxsub(int a[], int n)
{
    int i,maxsum,linesum;
 
    maxsum = max1num(a, n);
 
    if (maxsum <= 0)
        return maxsum;
 
    linesum = 0;
    for (i = 0; i < n; i++) {
        linesum += a[i];
 
        if (linesum < 0)
            linesum = 0;
        if (linesum > maxsum)
            maxsum = linesum;
    }
    return maxsum;
}
 
 
// min1num返回数组中最小值
int min1num(int a[], int n)
{
    int i, min;
    min = a[0];
    for (i = 1; i < n; i++)
        if (a[i] < min)
            min = a[i];
    return min;
}
 
//求数组a的最小子序列和
int minsub(int a[], int n)
{
    int i;
    int minsum, linesum;
 
    minsum = min1num(a,n);
 
    if (minsum >= 0)    //如果minsum >= 0的话，数组中没有负数，minsum即是最小子序列（只有一个元素minsum）
        return minsum;
 
    linesum = 0;
    for (i = 0; i < n; i++) {
        linesum += a[i];
        if (linesum > 0 && linesum > minsum)
            linesum = 0;
        if (linesum < minsum)
            minsum = linesum;
    }
    return minsum;
}
 
int main(void)
{
    int a[]={-324,23,23,111,23232,222,1111,555,-222,22,-88888};
    printf("%d\n",minsub(a,11));
 
    int b[]={324,23,-300,111,-121,2,-456,555,222,22,88888};
    printf("%d\n",minsub(b,11));
 
    int c[]={-324,23,23,111,23232,222,1111,555,-222,22,-88888};
    printf("%d\n",maxsub(c,11));
 
    int d[]={324,23,-300,111,-121,2,-456,555,222,22,88888};
    printf("%d\n",maxsub(d,11));
 
 
    return 0;
}

sasf