一个关于分治算法的问题

Question

比如有一个List L = [(0,1), (1, 0), (0, 1), (1, 1), (1, 2), (3, 1), (3, 1), (2, 2), (2, 3), (3, 2), (2, 3), (4, 3), (3, 4), (4, 4), (4, 5), (5, 5)]

包含N对两两一起的Integer

现在有 (ai,bi)∈L 和 (aj,bj)∈L

我们假设如果任意两对满足以下**三种情况其一**，就称这两组数是一对
ai=aj 并且 bi=bj
ai<aj
bi<bj
比如 (1,2) (1,1)就不是一对，因为任意一个条件都不满足

那么假设我们有一组中间的（ai，bi），在满足什么情况下我们可以直接停止搜索他的对子呢？

另外用**分治法**的话，给出一组数字，如何寻找他的一对数组呢？

Answer 1

 package com.test;  

import java.util.ArrayList;  
import java.util.List;  

public class MyTest02 {  
    public static void main(String[] args) {  
        int[] a = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };  
        int[] s = getMaxSummary(a, 0, 15);  
        for (int i = 0; i < s.length; i++) {  
            System.out.println(s[i]);  
        }  
    }  

    /** 
     * 程序主入口 
     * @param A 
     * @param low 
     * @param high 
     * @return 
     */  
    public static int[] getMaxSummary(int[] A, int low, int high) {  
        if (low == high) { // 如果長度就一個，那麼就把這個取出來  
            int[] result = { low, high, A[low] };  
            return result;  
        } else {  
            int middle = (int) Math.floor((low + high) / 2); // 获取中间值  
            int[] left = new int[3]; // 保存左边部分返回结果  
            int[] right = new int[3]; // 保存右边部分返回结果  
            int[] cross = new int[3]; // 返回交叉部分返回结果  
            left = getMaxSummary(A, low, middle);  
            right = getMaxSummary(A, middle + 1, high);  
            cross = getMaxCrossMid(A, low, high, middle);  
            if (left[2] >= right[2] && left[2] >= cross[2]) {   // 那部分大就用了那部分  
                return left;  
            } else if (right[2] >= left[2] && right[2] >= cross[2]) {  
                return right;  
            } else {  
                return cross;  
            }  
        }  
    }  

    /** 
     * 獲取最大子數組（一部分在左邊，一部分在右邊） 
     *  
     * @param A 
     * @param low 
     * @param high 
     * @param middle 
     * @return 
     */  
    public static int[] getMaxCrossMid(int[] A, int low, int high, int middle) {  
        int leftSum = Integer.MIN_VALUE;  
        int sum = 0; // 保存和的  
        int left = 0; // 记录左边位置  
        for (int i = middle; i >= low; i--) {  
            sum = sum + A[i];  
            if (sum > leftSum) { // 证明所加数字为正数，那么符合条件（因为最大子数组内正数越多指定越大）  
                leftSum = sum;  
                left = i;  
            }  
        }  

        int rightSum = Integer.MIN_VALUE;  
        int sum2 = 0;  
        int right = 0; // 记录右边位置  
        for (int i = middle + 1; i <= high; i++) {  
            sum2 = sum2 + A[i];  
            if (sum2 > rightSum) {  
                rightSum = sum2;  
                right = i;  
            }  
        }  

        int[] result = new int[3];  
        result[0] = left;  
        result[1] = right;  
        result[2] = leftSum + rightSum;  
        return result;  
    }  




}