By

文章目錄

已知数组x[ ]储存了一组整数，请写一个程序，找出在数组中连续元素的和中最大的一个。举例而言，如果有数组1，2，-6，3，-2，4，-1，3，2，-4，那么连续的元素和有1 + 2 = 3，1 + 2 + (-6) = -3，2 + (-6) = -4，。。。，但最大的就是3 + (-2) + 4 + (-1) + 3 + 2这一段，值为9。这个题目通常叫做最大连续元素和问题，或者叫做最大连续子数组。

一个自然的办法是使用双重循环，但是性能不好。这个问题要求O(n)解法，需要动点脑筋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int result = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            result = Math.max(result, sum);
        }
        return result;      
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

还有一种是分治的方法，效率慢一些

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
public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);    
    }
    public static int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

打赏作者

文章目錄