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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#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));
}