备案网站有哪些,免费网站建设模板,做网站需要学jsp,零食网站模板下载前言
本专栏主要通过“LeetCode 热题100”#xff0c;来捡起自己本科阶段的算法知识与技巧。语言主要使用c/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~
题目描述
题目链接
示例 1#xff1a;
输入#xff1a;nums [-2,1…前言
本专栏主要通过“LeetCode 热题100”来捡起自己本科阶段的算法知识与技巧。语言主要使用c/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~
题目描述
题目链接
示例 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
思路
属于动态规划的例图凭借着之前本科对于这题动态转移方程的记忆把代码写下来了。下面是官方的解法我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」那么很显然我们要求的答案就是 max 0≤i≤n−1 {f(i)}
因此我们只需要求出每个位置的 f(i)然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢我们可以考虑 nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段这取决于 nums[i] 和 f(i−1)nums[i] 的大小我们希望获得一个比较大的于是可以写出这样的动态规划转移方程 f(i)max{f(i−1)nums[i],nums[i]}
下面放出我的代码因为最近感觉对于C的语法捡起来差不多了于是之后的解题会用Java多一点。
class Solution {public int maxSubArray(int[] nums) {// 动态规划经典题最大子数组和int nums_size nums.length;// 最后一个数字为下标为i的之和int[] dp_nums new int[nums_size];// initdp_nums[0] nums[0];// 动态转移方程for (int i1;inums_size;i){if (dp_nums[i-1] 0){dp_nums[i] dp_nums[i-1] nums[i];}else{dp_nums[i] nums[i];}}//寻找最大值int maxSum -9999999;for (int i0;inums_size;i){maxSum Math.max(dp_nums[i], maxSum);}return maxSum;}
}
