53. Maximum Subarray

原题链接：https://leetcode.com/problems/maximum-subarray/description/
多种解答实现：

/**
 * Created by clearbug on 2018/2/26.
 *
 * 这道题目之前面试遇见过，现在却又忘记结题思路了。。。想到《剑指Offer》这本书上面有原题，那就看看书的作者的解题思路吧！
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();

        System.out.println(s.maxSubArray1(new int[]{-2, -1})); // -1
        System.out.println(s.maxSubArray1(new int[]{-1, -2})); // -1
        System.out.println(s.maxSubArray1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
        System.out.println(s.maxSubArray2(new int[]{-2, -1})); // -1
        System.out.println(s.maxSubArray2(new int[]{-1, -2})); // -1
        System.out.println(s.maxSubArray2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
        System.out.println(s.maxSubArray3(new int[]{-2, -1})); // -1
        System.out.println(s.maxSubArray3(new int[]{-1, -2})); // -1
        System.out.println(s.maxSubArray3(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
    }

    /**
     * 方法一：简单粗暴，效率低下，即遍历出所有子数组的和，然后求最大值
     *
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {
        int sum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int newSum = 0;
                for (int k = i; k <= j; k++) {
                    newSum += nums[k];
                }
                if (newSum > sum) {
                    sum = newSum;
                }
            }
        }
        return sum;
    }

    /**
     * 方法二：稍微优雅点了，就是判断之前的和是否需要的问题了
     *
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int maxSum = nums[0];

        int currSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int newSum = currSum + nums[i];
            if (newSum < nums[i]) {
                currSum = nums[i];
            } else {
                currSum = newSum;
            }
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return maxSum;
    }

    /**
     * 方法三：虽然实现和方法二大致相同，但是方法三却是运用了动态规划的思想，可能更容易理解一点吧
     *
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; // dp[i] means the maximum subarray ending with A[i];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < n; i++) {
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }

        return max;
    }

}