2019-05-23矩阵1

package 矩阵;

import java.util.Arrays;

public class Matrix {  // 寻找一个数组中最大连续子序列的和
    public static int MoreSum(int[] arr) {
        if(arr.length < 1 || arr == null) {
            return -1;
        }// 递推法
        int sum = arr[0];
        int tmp = sum;  // tmp就是这个元素对最大值的贡献
        for(int i = 1; i < arr.length; i++) {
            if(tmp >= 0) { // 大于0就是正的贡献留下与下一个值相加
                tmp = tmp + arr[i];
            }else {
                tmp = arr[i]; // 小于0就跳过这个值
            }
            if(tmp > sum) {
                sum = tmp;  // 记录最大的值
            }               
        }
        return sum;
    }
    public static int MoreArrsum(int[] arr) {
        if(arr.length < 1 || arr == null) {
            return -1;
        }
        int mostMax = arr[0];
        for(int i = 0; i < arr.length; i++) {
            int sum = arr[i];
            int tmpsum = sum;
            for(int j = i + 1; j < arr.length; j++) {
                sum = sum + arr[j];
                if(sum > tmpsum) {
                    tmpsum = sum;
                }
            }
            if(tmpsum > mostMax) {
                mostMax = tmpsum;
            }
        }
        return mostMax;
    }
    public static void main(String[] args) {
        int i = 0;
        while(i < 1000) {
            int[] fin = randomArr(1000, 1000);
            System.out.println(Arrays.toString(fin));
            equals(MoreArrsum(fin), MoreSum(fin));
            i++;
        }
        
    }
    public static int[] randomArr(int maxSize, int maxValue) {
        int[] a = new int[(int)((maxSize + 1)* Math.random())];
        for(int i = 0; i < a.length; i++) {
            a[i] = (int)((maxValue + 1) * Math.random()) - (int)((maxValue) * Math.random());
        }
        return a;
    }
    public static void equals(int res1, int res2) {
        if(res1 == res2) {
            System.out.println("Yes");
        }else {
            System.out.println("Sorry");
        }
    }
}