数据结构与算法解析习题2.12：最小子序列和，最小正序列和，最大子序列乘积

书上的最大子序列和还有最小子序列和，最小正序列和，最大子序列乘积，这四个基本上是最常问的题了。

这几个绕来绕去容易把人搞蒙，算法有相似但地方但是细微的差别导致结果不同，再此记录一下。


#include <stdio.h>

/** ------------------------ 最小子序列和 ------------------------ */

int minSequenceSum(const int A[],int N) {

    int minSum, thisSum, i;

    minSum = 0x7FFFFFFF; thisSum = 0;
    for (i = 0; i < N; i++) {
        thisSum += A[i];

        if (thisSum < minSum)
            minSum = thisSum;
        else if (thisSum > 0)
            thisSum = 0;

    }
    return minSum;
}

/** ------------------------ 最小正序列和 ------------------------
 * 1、连续子序列，2、序列和为正且最小
 * 思路：求出开始的一组子序列：｛-2｝，｛-2，11｝，
 *｛-2，11，-4｝， ｛-2，11，-4，13｝，｛-2，11，-4，13，-5｝，｛-2，11，-4，13，-5，-2｝
 * 剩下的子序列必然可以通过上面的这一组子序列相减获得
 * 所以要获得最小正子序列各，必然将上面的序列和排序后的相邻序列和相减所得
 * */


//要记录秩
typedef struct node {
    int value;
    int rank;
} nodes;

//快排
int quickSort(nodes a[],int low,int high){

    nodes pivotkey = a[low];

    while(low<high) {

        while(low < high && a[high].value >= pivotkey.value) --high;

        a[low] = a[high];

        while(low < high && a[low].value <= pivotkey.value) ++low;

        a[high] = a[low];
    }

    a[low] = pivotkey;

    return low;

}

//快排的递归
void Qsort(nodes a[],int low,int high) {
    if(low < high) {
        int temp = quickSort(a,low,high);
        Qsort(a,low,temp);
        Qsort(a,temp+1,high);
    }
}



int minPositiveSubSum(int a[],int len) {

    nodes b[len];

    int sum = 0;
    for(int i = 0; i < len; i++) {
        sum += a[i];
        b[i].value = sum;
        b[i].rank = i;
    }

    //将其排序 O(nlogn)
    Qsort(b,0,len - 1);

//    for(int i=0;i<len;i++){
//        printf("%d rank为%d    ",b[i].value,b[i].rank);
//    }
//    printf("\n");

    int min = b[0].value >= 0 ? b[0].value : b[len-1].value;

    for(int i = 1; i < len; i++) {
        //必须得够减
        if(b[i].rank > b[i-1].rank) {
            int temp = b[i].value-b[i-1].value;
            if(temp > 0 && temp < min) {
                min = temp;
            }
        }

    }
//    printf("最小正序列和为：%d \n",min);
    return min;
}



/** ------------------------ 最大子序列乘积 ------------------------ */

int max_int(int x, int y)
{
    return x > y ? x : y;
}

int min_int(int x, int y)
{
    return x < y ? x : y;
}

int maxSubProduct(int a[],int len) {

    int posMax = a[0];
    int negMax = a[0];
    int ret = a[0];

    for(int i=1; i < len; i++)
    {
        int tempPosMax = posMax;
        int tempNegMax = negMax;
        posMax = max_int(a[i], max_int(a[i] * tempPosMax, a[i] * tempNegMax));
        negMax = min_int(a[i], min_int(a[i] * tempPosMax, a[i] * tempNegMax));
        ret = max_int(ret,posMax);
    }

    return ret;

}



int main() {

    int arr1[] = {0,3,16,-7,8,-8,-9,-12,55,-11,99};

    printf("最小子序列和 = %d \n", minSequenceSum(arr1, 11));

    int arr2[]={-2,11,-4,13,-5,-2};

    printf("最小正序列和为 %d \n", minPositiveSubSum(arr2, 6));

    int arr3[]={2,3,-2,4};

    printf("最大子序列乘积 %d \n", maxSubProduct(arr3, 4));
}