剑指offer - 连续子数组的最大和(Java实现)

题目链接：https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&&tqId=11183&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先最暴力的方法就是遍历所有的子数组，同时记录当中的最大值，最后输出即可。

import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < n; ++ i) {
            int sum = 0;
            for(int j = i; j < n; ++ j) {
                sum += array[j];
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }
}

  思路二：找规律，首先我们可以记录一个连续子数组的和，根据这个和的变化进行相应的操作，那么我们可以通过一组样例来模拟这个过程。

  通过上图过程我们可以发现一定的规律，如果当前的和 sum < array[i]，此时我们就可以开始一段新的子数组，然后继续记录其和值，这样才能保证子数组的和可能是更大的。

import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        int ans = Integer.MIN_VALUE, sum = 0;
        for(int  i = 0; i < n; ++ i) {
            sum += array[i];
            if(sum < array[i]) sum = array[i];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

  思路三：通过思路二，我们可以想到使用 dp 的方式来对以 array[i] 为结尾的和值来进行一个计算。
  

import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        int[] dp = new int[n]; //以array[i]连续子向量和
        int ans = Integer.MIN_VALUE;
        for(int  i = 0; i < n; ++ i) {
            if(i == 0) dp[i] = array[i];
            else dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}