剑指 Offer 42. 第 9 天 动态规划（中等）
- 剑指 Offer 42. 连续子数组的最大和
-
- 题目思路
- 代码
-
- c++代码
- python代码
- 剑指 Offer 47. 礼物的最大价值
-
- 题目思路
- 代码
-
- c++代码
- python代码
剑指 Offer 42. 连续子数组的最大和 题目思路 不断用一个变量进行求和，如果求和结果小于0的话则等于当前元素，否则加上当前元素，求该变量的最大值
代码 c++代码
class Solution {
public:
int maxSubArray(vector& nums) {
int n = nums.size();
int sum=0;
int ans=-1000000;
for(int i=0;
i python代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
s = 0
ans = -1000000
for i in range(n):
if s<0 :
s = nums[i]
else :
s = s + nums[i];
ans=max(ans,s)
return ans
剑指 Offer 47. 礼物的最大价值 题目思路 很明显结果是从上一个和左边那个推过来的，选取最大值
代码 c++代码
class Solution {
public:
int maxValue(vector>& grid) {
if(!grid.size()||!grid[0].size())return 0;
int a[210][210]={0};
int n = grid.size();
int m = grid[0].size();
for(int i=1;
i<=n;
i++){
for(int j=1;
j<=m;
j++){
a[i][j]=max(a[i-1][j],a[i][j-1]);
a[i][j]+=grid[i-1][j-1];
}
}
return a[n][m];
}
};
python代码
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
if grid==None or grid[0]==None :
return 0
n =len(grid)
m = len(grid[0])
a = [[0]*210]*210
for i in range(1,n+1):
for j in range(1,m+1):
a[i][j] = max(a[i-1][j],a[i][j-1])
a[i][j] = a[i][j] + grid[i-1][j-1]
return a[n][m]
这篇文章如果对小伙伴们有帮助的话，希望点个赞支持一下~ 十分感谢~ 【剑指offer|剑指 Offer 42. 第 9 天 动态规划（中等）】
文章图片
推荐阅读
- 数据结构|数据结构 Java数据结构 ---- 堆(优先级队列)
- 深度学习校招面试总结|人工智能面试总结-传统图像算法
- 面试笔试|2022春招华为笔试题-（2）
- 深度学习|基于pytorch用yolov5算法实现目标检测与分割
- 卷积|图解（卷积神经网络数学原理解析）
- 算法|DeepMind联合UCL，推出2021强化学习最新课程
- LeetCode编程题解法汇总|力扣解法汇总18-四数之和
- LeetCode编程题解法汇总|力扣解法汇总553-最优除法
- MA117 科学统计