算法设计 最大子数组（序列）

Question

采用分治法，有没有简单的方法标记最大子序列的开始和结尾点。
即为可以输出子序列各个元素

Answer 1

在分治求和过程中，遇到更大的和值时，更新一下当前子数组下标就可以了

public class MaxSumSubarray {

    private static int binarySearch(int a[], int left, int right, MaxSumSubarray result) {
        int leftSum, rightSum, crossSum;
        if (left == right) {
            if (a[left] > result.sum) {
                result.sum = a[left];
                result.begin = left;
                result.end = right;
            }
            return a[left];
        } else {
            int mid = (left + right) / 2;
            leftSum = binarySearch(a, left, mid, result);
            rightSum = binarySearch(a, mid + 1, right, result);
            crossSum = crossBinarySearch(a, left, mid, right, result);
            if (leftSum >= rightSum && leftSum >= crossSum) {
                if (leftSum > result.sum) {
                    result.sum = leftSum;
                    result.begin = left;
                    result.end = mid;
                }
                return leftSum;
            } else if (rightSum >= leftSum && rightSum >= crossSum) {
                if (rightSum > result.sum) {
                    result.sum = rightSum;
                    result.begin = mid;
                    result.end = right;
                }
                return rightSum;
            } else {
                return crossSum;
            }
        }
    }

    public static MaxSumSubarray binarySearch(int[] a) {
        if (a == null || a.length == 0) {
            return null;
        }
        MaxSumSubarray result = new MaxSumSubarray();
        result.sum = binarySearch(a, 0, a.length - 1, result);
        return result;
    }

    private static int crossBinarySearch(int a[], int left, int mid, int right, MaxSumSubarray result) {
        int leftSum = 0;
        int max_left_sum = 0;
        int begin = mid, end = mid + 1;
        for (int i = mid; i >= left; i--) {
            leftSum += a[i];
            if (leftSum > max_left_sum) {
                begin = i;
                max_left_sum = leftSum;
            }
        }

        int rightSum = 0;
        int max_right_sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            rightSum += a[i];
            if (rightSum > max_right_sum) {
                end = i;
                max_right_sum = rightSum;
            }
        }

        int sum = max_left_sum + max_right_sum;
        if (sum > result.sum) {
            result.sum = sum;
            result.begin = begin;
            result.end = end;
        }
        return sum;
    }

    private int begin;

    private int end;

    private int sum;

    public MaxSumSubarray() {
        super();
        sum = Integer.MIN_VALUE;
    }

    /**
     * @return the begin
     */
    public int getBegin() {
        return begin;
    }

    /**
     * @return the end
     */
    public int getEnd() {
        return end;
    }

    /**
     * @return the sum
     */
    public int getSum() {
        return sum;
    }
}

我这里用java语言实现，如果用其他语言，可以将MaxSumSubarray用一个整形数组替换，

private int begin;

private int end;

private int sum;

这三个字段就用一个int[3]替换