本文主要是介绍[Java] 最大子序和，给定一个整数数组，找到一个具有最大和的连续子数组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

[Java] 最大子序和，给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 目的
• 分析
• 代码

目的

练习与动态规划的相关问题

分析

1. 无需考虑i、i-1、i-2通过分治的思想，考虑i和i-1之间的关系即可
2. 定义一个集合dp用于存放子串和的结果集，dp数组表示以i结尾的最大字串的和的集合
3. 求出dp集合中的最大值即可

代码

public int maxSubArray(int[] nums) {
    if(nums.length == 1){
        return nums[0];
    }
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(nums[0]);
    for(int i=1;i<nums.length;i++){
        if(dp.get(i-1)>0){
            Integer tem = dp.get(i-1) + nums[i];
            dp.add(tem);
        }else{
            dp.add(nums[i]);
        }
    }
    int res = dp.get(0);
    for(int i=1;i<dp.size();i++){
        if(dp.get(i) > res){
            res = dp.get(i);
        }
    }
    return res;
}

这篇关于[Java] 最大子序和，给定一个整数数组，找到一个具有最大和的连续子数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！