剑指 Offer42.连续子数组的最大和

剑指 Offer42.连续子数组的最大和

文章目录

• • • • 剑指Offer42.连续子数组的最大和
      • • 题目描述
        • 测试示例
        • 解题思路和代码示例
        • • 解题思路
          • 代码参考

剑指Offer42.连续子数组的最大和 题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

测试示例

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路和代码示例 解题思路

这里注意一个或连续多个整数组成的子数组我们可以从两方面考虑，从子数组首开始，丛子数组的尾部入手，但是显然从前入手，根本找不到递推关系，所以肯定是从子数组的最后一个数入手，这才能找到递推关系式，一般动态规划也是这样，因为需要遍历数组的原因，所以肯定是寻找和已经遍历的数的关系。

​

代码参考

class Solution {
    public int maxSubArray(int[] nums) {

        
        int max = nums[0];
         //状态定义
         int[] dp = new int[nums.length];
         //初始化
         dp[0] = nums[0];
         //遍历顺序
         for(int i=1;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5651112.html