[Leetcode53]最大子数组和
2023-03-31 10:45:20 时间
1.题目
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。
2.题目分析
本道题也是一道动态规划题目。
设dp[i]为该位置下的最大连续子数组之和。
dp[i]=nums[i](当nums[i]>(dp[i-1]+nums[i]))
dp[i]=nums[i]+dp[i-1](当nums[i]<=(dp[i-1]+nums[i]))
max=dp[i](max<dp[i])
3.代码
class Solution {
public int maxSubArray(int[] nums) {
int length=nums.length;
int dp[]=new int[length];
int max=nums[0];
dp[0]=nums[0];
if(length ==1)
{
return max;
}
for(int i=1;i<length;i++)
{
int temp=nums[i]+dp[i-1];
if(nums[i]>(temp))
dp[i]=nums[i];
else
dp[i]=temp;
if(max<dp[i])
max=dp[i];
}
return max;
}
}
相关文章
- 放弃了 7 年的 Java,投身互联网做 PHP,我是如何成为创业公司的 CTO?
- 遗传算法的基本概念和实现(附 Java 实现案例)
- Java人员正确使用IntelliJ IDEA的方式
- 图说Java —— 理解Java机制最受欢迎的8幅图
- 什么时候使用Lambda函数?
- 知加一周精选:一个程序员一生最多只需三种编程语言
- 快速入门Kotlin的11招
- Kotlin函数与函数式编程浅析
- Java异常的深入研究与分析
- Java开发中异常处理的更优实践
- Java多线程之内置锁与显示锁
- Java多线程之synchronized关键字详解
- Java高级特性之反射学习总结
- 你应该使用Django admin的9个理由
- Java反射机制应用实践
- 深入探讨Java中的异常与错误处理
- 研究学习Kotlin的一些方法
- 数据显示Java热度持续下落,日子屈指可数?
- 不需要jre运行Java?你没看错!
- 2017年5月编程语言排行榜:Java与C语言优势正开始缩小