512、java-求最大子数组

求最大子数组

方式一：穷举出所有子数组

 public static void main(String[] args) {
        int[] arr = new int[]{1,2,-4,5,-3,5,3,-9,3};
        querySubArr(arr);
        querySubArrExhaustively(arr);
    }

    /**
    　　* @description: 穷举的方式，罗列出所有子数组
    　　* @param ${tags}
    　　* @return ${return_type}
    　　* @throws
    　　* @author chenjy
    　　*/
    public static void querySubArrExhaustively(int[] arr) {
        if (arr == null || arr.length == 0)
            throw new IllegalArgumentException("数组为空");
        //1. 子数组容器
        Map<Integer,String> map = new HashMap<>();
        //穷举出所有子数组
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            String value = arr[i]+"";
            map.put(key,value);
            for (int j = i+1; j < arr.length ; j++){
                key = key+arr[j];
                value = value+"_"+arr[j];
                map.put(key,value);
            }
        }
        //比较最大的key
        Set<Integer> keySet = map.keySet();
        Integer max = keySet.stream().max(new ComparableComparator<>()).get();
        //取子数组
        System.out.println("max:"+max);
        System.out.println("maxSubArray:"+ JSON.toJSONString(map.get(max).split("_")));
    }

方式二：O(N)复杂度

理解：当前子数组、最大子数组两个概念
int[] arr = new int[]{1,2,-4,5,-3,5,3,-9,3};

例如：
从坐标 0 开始，最大、当前子数组都是1

1+2 最大、当前子数组都是 1、2

1+2-4，则当前子数组是1、2、3；最大子数组1、2

1+2-4+5，这里有个概念 a+b+c<c 则可以推出， c > a+b，所以当前子数组需要初始化，从5开始，因为 a+b+c<c，此时当前子数组为5,又因为1+2 < 5,所以最大子数组也变为了5，如果这个坐标数是2，则最大子数组不变

 /**
   　　* @description: 获取数组中最大和的子数组，O(n)复杂度
   　　* @author chenjy
   　　*/
   public static void querySubArr(int[] arr) {
       if (arr == null || arr.length == 0)
           throw new IllegalArgumentException("数组为空");
       //1. 定义
       //最大子数组和
       int max = arr[0];
       //当前子数组和
       int curr = arr[0];
       //数组字符串
       String maxStr = arr[0]+"_";
       String subStr = arr[0]+"_";
       //遍历数组
       for (int i = 1; i < arr.length; i++) {
           curr = curr + arr[i] > arr[i] ? curr+arr[i] : arr[i];
           //2. 计算 a+b+c < c  那么可知a、b只会减小c的值，所以a、b舍去，从c开始
           if(curr == arr[i]){
               //重新计算当前子字符串
               subStr="";
           }
           subStr += arr[i]+"_";
           //当前子数组和，大于前一段的和则替换为最大子数组和
           if(curr > max){
               max = curr;
               maxStr=subStr;
           }
       }
       System.out.println("max:"+max);
       System.out.println("maxSubArray:"+ JSON.toJSONString(maxStr.split("_")));
   }

max:10
maxSubArray:["5","-3","5","3"]
max:10
maxSubArray:["5","-3","5","3"]