编程之美：求子数组的最大和

技术 > 数据结构 Data Structure

发布时间 : 2020-04-18 20:33

字数:719 阅读 :78 评论:

1、算法描述
2、C编程实现
THE END!

本文目录

1、算法描述
2、C编程实现
THE END!

1、算法描述

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如:
输入的数组为1,-2,3,10,-4,7,2,-5
和最大的子数组为3,10,-4,7,2
因此输出为该子数组的和18。

2、C编程实现

针对该问题，采用了暴力穷举解法、分治算法、动态规划算法求解。

// 方法一：暴力解法 时间复杂度O(N^3)
int maxSubarray_org(int a[], int size)
{
    int iMaxSum = INT_MIN;
    int sum = 0;
    int i = 0, j = 0, k = 0;

    for (i = 0; i < size; i++)
    {
        for (j = i; j < size; j++)
        {
            sum = 0;
            for (k = i; k <= j; k++)
            {
                sum += a[k];
            }
            if (sum > iMaxSum)
                iMaxSum = sum;
        }
    }
    return iMaxSum;
}

// 方法一：暴力解法 优化版本 时间复杂度O(N^2)
int maxSubarray_org_opt(int a[], int size)
{
    int iMaxSum = INT_MIN;
    int sum = 0;
    int i = 0, j = 0, k = 0;

    for (i = 0; i < size; i++) // 从第i个位置开始寻找连续数据的最大值
    {
        sum = 0;
        for (j = i; j <= size; j++)
        {        
            sum += a[j];
            if (sum > iMaxSum)
                iMaxSum = sum;
        }
    }
    return iMaxSum;
}
// 方法二：采用分治的思想 时间复杂度 O(2*N)
int maxSubarray(int a[], int size)
{
    int iMaxSum = 0;
    int iLocalSum = 0;
    int i = 0;

    for(i = 0; i < size; i++)
    {
        iLocalSum += a[i];
        if(iLocalSum < 0)
        {
            iLocalSum = 0;  // 局部和出现小于0的情况，则设置为0
        }
        if(iLocalSum > iMaxSum)
        {
            iMaxSum = iLocalSum; // 更新局部最大和
        }
    }

    if(iMaxSum == 0)    // 子数组最大和出现负数情况下，取数组中的最大值。
    {
        iMaxSum = a[0];

        for(i = 1; i < size; i++)
        {
            if(iMaxSum < a[i])
                iMaxSum = a[i];
        }
    }

    return iMaxSum;
}

int max(int x, int y)
{
    return (x>y) ? x : y;
}
// 方法三：动态规划  时间复杂度O(N) 空间复杂度O(2*N)
int maxSubarray_DP(int a[], int size)
{
    int Start[50];
    int All[50];
    int i = 0;

    Start[size-1] = a[size-1];
    All[size-1] = a[size-1];

    for (i = size -2; i >= 0; i--)
    {
        Start[i] = max(a[i], a[i]+Start[i+1]);
        All[i] = max(Start[i], All[i+1]);
    }
    return All[0];
}

// 方法四： 动态规划 优化版本 时间复杂度 O(N) 空间复杂度O(1)
int maxSubarray_DP_opt(int a[], int size)
{
    int nStart = 0;
    int nAll = 0;
    int i = 0;
    nStart = a[size-1];
    nAll = a[size-1];

    for(i = size-2; i >=0; i--)
    {
        nStart = max(a[i], nStart + a[i]);
        nAll = max(nStart, nAll);
    }
    return nAll;
}

// 方法四：动态规划 另一种简便写法，这种写法体现了数学之美和编程之美！
int maxSubarray_DP_opt_v2(int a[], int size)
{
    int nStart = 0;
    int nAll = 0;
    int i = 0;
    nStart = a[size-1];
    nAll = a[size-1];

    for(i = size-2; i >=0; i--)
    {
        if (nStart < 0)
        {
            nStart = 0;
        }
        nStart += a[i];
        if (nStart > nAll)
        {
            nAll = nStart;
        }
    }
    return nAll;
}


//test demo
int main(int argc, char *argv[])
{
#if 0
    int array[8] = {1,-2,3,10,-4,7,2,-5};
    //int array[8] = {-2, 5, 3, -6, 4, -8, 6};
#else
    int array[8] = {-1,-2,-3,-10,-4,-7,-2,-5};
#endif

    int max_sum = 0;

    max_sum = maxSubarray_DP_opt_v2(array, 8);
    printf("max_sum_subarray: %d    \n", max_sum);
    return 0;
}c arduino复制代码
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
156

THE END!

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com