求最大子数组和

求整数数组中连续子序列之和最大值,其中整数数组可以为正数、负数、0
在线调试: http://www.k6k4.com/code/qshow/aangoolmh1508082971707

解决:

public class Main {

    public static void main(String[] args) {
        int[] input = new int[] {-2, 4, -2, 7, -6, -1};
        System.out.println(solution2(input, input.length));
    }

    //暴力破解法
    public static int solution1(int[] input, int n) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += input[j];
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }
        return maxSum;
    }

    //较优解
    public static int solution2(int[] input, int n) {
        int maxSum = input[0], beforSum = input[0];
        for (int i = 1; i < n; i++) {
            if (beforSum < 0) {
                beforSum = input[i];
            } else {
                beforSum += input[i];
            }
            if (beforSum > maxSum) {
                maxSum = beforSum;
            }
        }
        return maxSum;
    }

}


分享本文