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

/**
 * 问题的关键是找到状态方式，找到状态方程后问题就迎刃而解
 * 状态方程如下：
 * b[j]表示第j处，以a[j]结尾的子序列的最大和
 * b[j]=max(a[j] + b[j-1], a[j])
 * b数据的最大值即为问题的解
 * 问题转换为求解b数组
 * 时间复杂度为O(1)，空间复杂度为(n)，空间复杂度可以降为O(1)，为了使程序易读，不做调整
 */
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
		return 0;
	}
	int *b = new int[n];
	b[0] = A[0];
	int max_b = b[0];
	for (int i=1; i<n; i++)
	{
		b[i] = std::max(A[i] + b[i-1], A[i]);
		if (max_b < b[i])
		{
			max_b = b[i];
		}
	}
	delete[] b;
	return max_b;
}

  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

class Solution {
public:
    int compare_array[4];

    int maxSubArray(int A[], int n) {
        return maxSubArray(A, 0, n - 1);
    }

    /**
     * leetcode not support stdarg.h
     */
    int max(int count, ...)
    {
        va_list ap;
        va_start(ap, count);
        int max = INT_MIN;
        for (int i=0; i<count; i++)
        {
            int temp = va_arg(ap, int);
            if (max < temp)
            {
                max = temp;
            }
        }
        va_end(ap);
        return max;
    }

    int max_compare_array()
    {
        int max_num = compare_array[0];
        for (int i=1; i<4; i++)
        {
            if (max_num < compare_array[i])
            {
                max_num = compare_array[i];
            }
        }
        return max_num;
    }

    int maxSubArray(int A[], int begin, int end)
    {
        //printf("begin : %d, end : %d\n", begin, end);
        if (begin == end)
        {
            return A[begin];
        }
        else if ((end - begin) == 1)
        {
            //return max(3, A[begin], A[begin] + A[end], A[end]);
            compare_array[0] = A[begin];
            compare_array[1] = A[begin] + A[end];
            compare_array[2] = A[end];
            compare_array[3] = INT_MIN;
            return max_compare_array();
        }
        int middle = (begin + end) / 2;
        // 处理左边子数组
        int max_left = maxSubArray(A, begin, middle);
        // 处理右边子数组
        int max_right = maxSubArray(A, middle + 1, end);
        // 处理跨越中点的情况
        int max_cross = maxCrossMiddle(A, begin, end);

        printf("begin : %d, end : %d, max_left = %d, max_right = %d, max_cross = %d\n", begin, end, max_left, max_right, max_cross);

        // 返回三者中的最大值
        compare_array[0] = max_left;
        compare_array[1] = max_right;
        compare_array[2] = max_cross;
        compare_array[3] = INT_MIN;
        return max_compare_array();
    }

    /**
     * 处理跨越中点的情况
     */
    int maxCrossMiddle(int A[], int begin, int end)
    {
        if (begin == end)
        {
            return A[begin];
        }
        int middle = (begin + end) / 2;
        // 求得[begin -- middle-1]的最大值
        int max_left = A[middle - 1];
        int sum = 0;
        for (int i=middle - 1; i>=begin && i >= 0; i--)
        {
            sum += A[i];
            if (max_left < sum)
            {
                max_left = sum;
            }
        }

        // 求得[middle+1 -- end]的最大值
        int max_right = A[middle + 1];
        sum = 0;
        for (int i=middle + 1; i<=end; i++)
        {
            sum += A[i];
            if (max_right< sum)
            {
                max_right = sum;
            }
        }

        compare_array[0] = A[middle];
        compare_array[1] = A[middle] + max_left;
        compare_array[2] = A[middle] + max_right;
        compare_array[3] = A[middle] + max_left + max_right;
        return max_compare_array();
    }
};

 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

int maxSubArray(int A[], int n) {
	if (n == 0)
	{
	    return 0;
	}
	int current_sum = 0;
	int max_sum = INT_MIN;

	for (int i=0; i<n; i++)
	{
	    if (current_sum <= 0)
	    {
		current_sum = A[i];
	    }
	    else
	    {
		current_sum += A[i];
	    }
	    if (current_sum > max_sum)
	    {
		max_sum = current_sum;
	    }
	}
	return max_sum;
}