Java教程

[Java] 最大子序和,给定一个整数数组,找到一个具有最大和的连续子数组

本文主要是介绍[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] 最大子序和,给定一个整数数组,找到一个具有最大和的连续子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!