Leetcode53-求子数组最大和

这是一个比较经典的题目，一般最简单的想法是列举所有的可能情况，再做统计，也是最笨拙的方法。按题目要求来说一个数组。比如ax = {a1,a2,a3,a4....an}，其中{a1},{a2},{a3}...{a1,a2}...{a1,a2,a3}..等等都是子数组，这种情况合计有(n+1)*n/2种 (复杂度n^2)， 每个子数组还要计算和，则算法的复杂度是n^3。根据运行结果，含1000个元素的数组，需要执行大概330-500毫秒。
但是这个题目有实现O(n)复杂度的解法，即使用贪心法，求最优解。思路是当找到的数组最大和小于0，则重置为0继续，这块需要加深理解。
以下是两种不同复杂度的解法代码：

/**
 * Created by igoso on 18-3-22.
 Find the contiguous sub array within an array (containing at least one number) which has the largest sum.
 For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
 the contiguous sub array [4,-1,2,1] has the largest sum = 6.
 求最大的子数组元素的和，实现n^3的解法，通过199/202的case，无法通过，1000个元素需要330+ms;
 实现O(n)的解法，通过，1000个元素需要0.3+ms,俗称的贪心法处理，比较惊艳;
 */
public class Leet53 {
    public static void main(String[] args) {
//        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        //4,-1,2,1
        int[] arr = new int[1000];
        Random r = new Random(1000);
        for (int i = 0; i < 1000; i++) {
            arr[i] = -r.nextInt(1000) + r.nextInt(1000);
        }
        long start = System.nanoTime();
        System.out.println(start);
        System.out.println(maxSubArray2(arr));
        System.out.println("end" + (System.nanoTime() - start));
    }

    //O(n^3)
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        double max = nums[0];
        double sum = 0;
        int step = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = j; k < step + j && k < nums.length; k++) {
                    sum += nums[k];
                }
                max = (sum > max) ? sum : max;
                sum = 0;
            }
            step++;
        }

        if (max > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }

        if (max < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int) max;
    }

    //O(n)
    public static int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;

        //如果和为负数，则省略继续
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > max) {
                max = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }

        return max;
    }
}