利用分治策略解决最大子序列和问题（代码）（Java）

《算法导论》学习记录

/**
 * 利用 分治策略 解决 最大子数组问题
 */
public class _1MaximumSubarrayProblem {
    public static LHS FIND_MAX_CROSSING_SUBARRAY(int[] A, int low, int mid, int high) { // 处理第三种情况的方法
        int left_sum = Integer.MIN_VALUE;
        int max_left = mid; // 左边界
        int sum = 0;
        for(int i = mid; i >= low; i--) { // 从中点往左找
            sum += A[i];
            if(sum > left_sum) {
                left_sum = sum;
                max_left = i;
            }
        }

        int right_sum = Integer.MIN_VALUE;
        int max_right = mid + 1; // 右边界
        sum = 0;
        for(int j = mid + 1; j <= high; j++) { // 从中点 + 1位往右找
            sum += A[j];
            if(sum > right_sum) {
                right_sum = sum;
                max_right = j;
            }
        }
        return new LHS(max_left, max_right, left_sum + right_sum);
    }

    public static LHS FIND_MAXIMUM_SUBARRAY(int[] A, int low, int high) {
        if(high == low) {
            LHS tmp = new LHS(low, high, A[low]);
            return tmp;
        }

        int mid = (low + high) / 2;
        LHS Left_Tmp = FIND_MAXIMUM_SUBARRAY(A, low, mid);  // 第一种情况，全在左边
        LHS Right_Tmp = FIND_MAXIMUM_SUBARRAY(A, mid + 1, high); // 第二种情况，全在右边
        LHS Cross_Tmp = FIND_MAX_CROSSING_SUBARRAY(A, low, mid, high); // 第三种情况，横跨中点

        if(Left_Tmp.sum >= Right_Tmp.sum && Left_Tmp.sum >= Cross_Tmp.sum) {
            return Left_Tmp;
        }
        else if(Right_Tmp.sum >= Left_Tmp.sum && Right_Tmp.sum >= Cross_Tmp.sum) {
            return Right_Tmp;
        }
        else {
            return Cross_Tmp;
        }
    }

    public static void main(String[] args) {
        int[] A = new int[]{ -1, -2, -3, -4 };
        LHS ans = FIND_MAXIMUM_SUBARRAY(A, 0, A.length - 1);
        // 如果A数组全负，则返回最大的负数
        System.out.printf("left:%d right:%d sum:%d\n", ans.low, ans.high, ans.sum);
    }
}

class LHS { // 用于记录在某一段区间的和
    public int low; // 左边界
    public int high; // 右边界
    public int sum; // 区间A[low..high]的总和

    public LHS(int l, int h, int s) {
        low = l;
        high = h;
        sum = s;
    }
}