本文共 730 字，大约阅读时间需要 2 分钟。

1. 本题知识点

动态规划

2. 题目描述

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

3. 解题思路

本题可以看做是一个多阶段决策找最优解的问题，因此可以用典型的动态规划思想来求解。

用 res[i] 表示以第 i 个元素结尾的子数组的最大和，那么有以下递推公式：

res[i]=max(res[i-1]+data[i], data[i])

这个公式的含义是：当以第 i-1 个数字结尾的子数组中所有数字的和小于 0 时，把这个负数与第 i 个数累加，则得到的和比第 i 个数字本身还要小，所以这种情况下 res[i] 就是第 i 个数字本身。反之，如果以第 i-1 个数字结尾的子数组中所有数字的和大于 0，则与第 i 个数字累加就得到以第 i 个数字结尾的子数组中所有数字的和。

4. 代码

public class Solution {
       public int FindGreatestSumOfSubArray(int[] array) {
           int max = array[0];        for (int i = 1; i < array.length; i++) {
               if (array[i - 1] > 0) {
                   array[i] += array[i - 1];            }            max = Math.max(max, array[i]);        }        return max;    }}

转载地址：http://rdjvb.baihongyu.com/