Java 连续子数组的最大和详解

连续子数组的最大和

题目描述

输入一个非空整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)

解法

动态规划法。

res[i] 表示以第 i 个数字结尾的子数组的最大和,那么求出 max(res[i]) 即可。


/**
 * @author bingo
 * @since 2018/12/7
 */

public class Solution {
    /**
     * 求连续子数组的最大和
     *
     * @param array 数组
     * @return 最大和
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        int[] res = new int[n];
        res[0] = array[0];
        int max = res[0];
        for (int i = 1; i < n; ++i) {
            res[i] = res[i - 1] > 0 ? res[i - 1] + array[i] : array[i];
            max = Math.max(max, res[i]);
        }
        return max;
    }
}

测试用例

  1. 功能测试(输入的数组中有正数也有负数;输入的数组中全是正数;输入的数组中全是负数);
  2. 特殊输入测试(表示数组的指针位为空指针)。

教程来源于Github,感谢apachecn大佬的无私奉献,致敬!

技术教程推荐

持续交付36讲 -〔王潇俊〕

邱岳的产品实战 -〔邱岳〕

NLP实战高手课 -〔王然〕

跟月影学可视化 -〔月影〕

重学线性代数 -〔朱维刚〕

Spring编程常见错误50例 -〔傅健〕

如何讲好一堂课 -〔薛雨〕

郭东白的架构课 -〔郭东白〕

结构会议力 -〔李忠秋〕