[数据结构与算法]剑指offer - 连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

示例

输入：[1,-2,3,10,-4,7,2,-5]
返回值：18

说明：
输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。 

算法思路

这题是动态规划的解题思路。

1. 定义 dp [] 数组，dp[i] 表示以 array[i] 结尾的连续子数组和
2. 初始化dp[] 数组，dp[0] = array[0]。
3. 定义状态转移方程。当 dp[i-1] >= 0 时，则dp[i] = dp[i-1]+array[i]。当dp[i-1] <= 0 时，dp[i] = array[i]

代码实现

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //定义dp[]数组
        int [] dp = new int[array.length];
        //初始化dp[]数组
        dp[0] = array[0];
        //res变量记录最大值。初始为dp[0]
        int res = dp[0];
        //状态转移方程
        for(int i=1;i<array.length;i++){
            if(dp[i-1]>=0){
                dp[i] = dp[i-1] + array[i];
            }else{
                dp[i] = array[i];
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}