- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
一.最大子数组和
二. 连续子数组的最大值II
三.子矩阵最大累加和
四.打家劫舍
五.乘积最大的子数组
六.乘积为正数最长子数组
1.对应letecode链接
53. 最大子数组和 - 力扣(LeetCode)
2.题目描述:
3.解题思路⭐⭐⭐
在之前的博客中我们提到了子数组问题的解法:一般子数组问题就是以某个位置开头怎么样,或者以某个位置结尾怎么样。在本题中我们可以这样想必须以i位置结尾的情况下最大累加和是多少。每个位置都这么搞最大累加和一定就在其中,那么每个位置的最大累计和又该如何求得?其实非常的简单必须以i位置结尾情况下的最大累加和有两种情况:
情况一:只要i位置的数字因为i位置前面的数可能都是负数
情况二:要必须以i-1位置结尾的情况下的累加和+当前位置的累加和。
这样我们就可以得到一个dp方程:dp[n] = Max(dp[n - 1] + arr[n], arr[n]);
对应动图:
4.对应代码:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int N=nums.size();
vector<int>dp(N);
dp[0]=nums[0];
//dp[i]的含义为必须以i位置结尾的情况下最大累加和是多少
int maxSum=nums[0];//记录最大的累加和
for(int i=1;i<N;i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
maxSum=max(maxSum,dp[i]);
}
return maxSum;
}
};
优化版本:数组压缩
如果有某一段子数组的累加和小于0了那么取得最大累加和的子数组一定不会包含它。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum=0;
int maxSum=nums[0];
for(int i=0;i<nums.size();i++){
sum+=nums[i];
maxSum=max(sum,maxSum);
sum=sum<0?0:sum;
}
return maxSum;
}
};
1.对应OJ链接
连续子数组的最大和(二)_牛客题霸_牛客网 (nowcoder.com)
2.题目描述:
3.解题思路:
本题思路和上面那题基本一模一样,只不过本题需要记录最长的那个子数组是谁。在这里我们只需要定义开头位置的变量和结尾位置的变量,将这两个变量维护好即可。
4.对应代码:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// write code here
int start=0;
int tmpStart=0;//记录开始位置和结束位置
int end=0;
int tmpEnd=0;
int sum=array[0];
int maxSum=array[0];
for(int i=1;i<array.size();i++){
if(sum>=0){
sum+=array[i];
tmpEnd=i;
}
else{
sum=array[i];
tmpEnd=i;
tmpStart=i;
}
if(sum>=maxSum){
maxSum=sum;
end=tmpEnd;
start=tmpStart;
}
}
vector<int>ans(end-start+1);
for(int i=0;i<ans.size();i++){
ans[i]=array[i+start];
}
return ans;
}
};
1.对应OJ链接
子矩阵的最大累加和问题_牛客题霸_牛客网 (nowcoder.com)
2.题目描述:
3.解题思路
本题其实上上面那题的升级版:同样的我们可以这样搞必须以0行做地基且必须以0行做地基子矩阵的最大累加和是多少,必须以0~1两行做地基且必须以0~1两行做地基子矩阵的最大累加和是多少。我们依次枚举答案一定就在其中。在这里0~1两行我们可以使用数组压缩在用上面那题的模板即可具体请看代码:
4.对应代码:
#include<iostream>
#include<limits.h>
#include<vector>
using namespace std;
int main()
{
int M,N;
cin>>M>>N;
vector<vector<int>>matix(M,vector<int>(N));
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin>>matix[i][j];
}
}
int maxSum=INT_MIN;
for(int i=0;i<M;i++){
vector<int>sum(matix[0].size());
for(int j=i;j<M;j++){//i.....j范围做地基的最大累加和
int cur=0;
for(int k=0;k<N;k++){
sum[k]+=matix[j][k];//数组压缩
cur+=sum[k];
maxSum=max(maxSum,cur);
cur=cur<0?0:cur;
}
}
}
cout<<maxSum<<endl;
return 0;
}
1.对应letecode链接
198. 打家劫舍 - 力扣(LeetCode)
2.对应题目描述:
3.解题思路:
本题和上面那题的思想是一样的同样是对应i位置怎么样。
dp[i]表示0-i能偷的最大金额,dp[i]由三种情况中的最大值转移过来
1.dp[i - 2] + nums[i] 表示偷当前位置,那么i-1的位置不能偷,而且需要加上dp[i-2],也就是前i-2个房间的金钱
2.dp[i - 1]表示不偷当前位置,只偷i-1的房间。
3.只偷当前位置的数
4.对应代码:
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==1){
return nums[0];
}
vector<int>dp(nums.size());
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
int maxRet=max(dp[0],dp[1]);
for(int i=2;i<nums.size();i++){
dp[i]=max(nums[i],max(dp[i-1],dp[i-2]+nums[i]));
maxRet=max(maxRet,dp[i]);
}
return maxRet;
}
};
1.对应letecode链接
152. 乘积最大子数组 - 力扣(LeetCode)
2.题目描述:
3.解题思路:
本题依然是子数组问题:子数组问题一般都是以谁谁结尾怎么样或者开头怎么样。在这里我们依然是考虑每个位置结尾的情况怎么样,在这里我们求必须以每个位置结尾的情况下最大乘积是多少?我们从0下标一直枚举到最后那么答案一定就在其中 。由于负数和负数乘起来有可能变成正数,所以我们需要定义两个变量来记录最小乘积和最大乘积。
4.对应代码:
class Solution {
public:
int maxProduct(vector<int>& nums) {
int Maxans=nums[0];//记录全局的最大乘积
int maxval=nums[0];
int minval=nums[0];
//求子数组必须以i为位置结尾的情况下最大的答案是多少
for(int i=1;i<nums.size();i++)
{
int maxEnd=maxval*nums[i];
int minEnd=minval*nums[i];
maxval=max(max(maxEnd,minEnd),nums[i]);
minval=min(min(maxEnd,minEnd),nums[i]);
Maxans=max(Maxans,maxval);
}
return Maxans;
}
};
1.对应letecode链接
1567. 乘积为正数的最长子数组长度 - 力扣(LeetCode)
2.题目描述:
3.解题思路:
本题和上题一样同样的是子数组问题:同样的是以某个位置结尾如何如何。用两个数组记录到当前位置乘积为正数的最长子数组的长度和乘积为负数的最长子数组长度,每到一个位置考虑当前位置的正负和前一个位置的最长子数组的关系 。具体请看代码
4.对应代码:
class Solution {
public:
int getMaxLen(vector<int>& nums) {
if(nums.size()==1){
return nums[0]<=0?0:1;
}
int N=nums.size();
vector<int>negetive(N);
vector<int>positive(N);
negetive[0]=nums[0]<0?1:0;
positive[0]=nums[0]>0?1:0;
//negetive[i]代表的是[0.....i]范围内乘积为负数的最长长度
//positive[i]代表的是[0....i]范围上乘积为正数的最长长度
int maxLen=0;
for(int i=1;i<N;i++){
if(nums[i]<0){
positive[i]=negetive[i-1]==0?0:negetive[i-1]+1;
negetive[i]=positive[i-1]+1;
}
else if(nums[i]==0){
positive[i]=0;
negetive[i]=0;
}
else{
positive[i]=positive[i-1]+1;
negetive[i]=negetive[i-1]==0?0:negetive[i-1]+1;
}
maxLen=max(maxLen,positive[i]);
}
return maxLen;
}
};
我想使用 NetworkX Graph 对象作为 Python dict 中的键。但是,我不希望默认的比较行为(即通过对象的地址)。相反,我希望同构图是 dict 中相同元素的键。 此行为是否已在某处
这个问题已经有答案了: What is the most effective way for float and double comparison? (33 个回答) 已关闭 7 年前。 在您认为我
我正在学习 C 编程,为了练习,我找到了一个需要解决的任务。这有点像一个游戏,有人选择一个单词,其他人猜测字母。我必须检查有多少给定的单词可能是所选单词的正确答案。 输入: 3 3//数字 n 和 m
我两天前开始学习C,在做作业时遇到了问题。我们的目的是从字符数组中获取字符列表,并通过计算连续字符并将其替换为数字来缩短它。对“a4b5c5”说“aaaabbbbbccccc”。这是我到目前为止的代码
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
为什么我在 if 中的比较不起作用?答案应该是 8 但它返回 0。 function findMissing(missingArray){ var getArray = missing
我想知道为什么以下 JavaScript 比较会给出不同的结果。 (1==true==1) true (2==true==2) false (0==false==0) false (0==false)
我想知道是否有人可以帮助我完成这个程序。编写一个接受两个字符串的函数。该函数应该将这两个字符串与字典顺序上排在第一位的字符串组合起来。两个字符串之间应该有一个空格。在一行上打印结果字符串。在一行上打印
有谁知道一个免费的开源库(实用程序类),它允许您比较一个 Java bean 的两个实例并返回一个属性列表/数组,这两个实例的值不同?请发布一个小样本。 干杯 托马斯 最佳答案 BeanCompara
我是java新手。任何人都可以给出以下类声明的含义 public class ListNode, V> { K key; V value; ListNode next;
我需要用 C 语言计算和比较 3 种不同大小(100 * 100、1000 * 1000 和 10000 * 10000)的 2 个矩阵相乘的执行时间。我编写了以下简单代码来为 1000 * 1000
当我在 ACCESS 2007 中运行以下 SQL 时 Select Location, COUNT(ApartmentBuildings) AS TotalIBuildingsManaged Fro
根据我对互斥锁的了解——它们通常提供对共享资源的锁定功能。因此,如果一个新线程想要访问这个锁定的共享资源——它要么退出,要么必须不断轮询锁(并在等待锁时浪费处理器周期)。 但是,监视器具有条件变量,它
通常在编程中,不应该比较浮点数据类型是否相等,因为存储的值通常是近似值。 由于两个非整数 Oracle NUMBER 值的存储方式不同(以 10 为基数),是否可以可靠地比较它们是否相等? 最佳答案
使用 PowerShell 时,我们偶尔会比较不同类型的对象。一个常见的场景是 $int -eq $bool (即其中 0 -eq $false 、 0 -ne $true 和任何非零值仅等于真,但不
#include #define MAX 1000 void any(char s1[], char s2[], char s3[]); int main() { char string1[
我想比较两个日期。 从这两个日期中,我只使用 ToShortDateString() 获取日期组件, 如下所示。现在的问题是当我比较两个日期时。它的 throw 错误—— "Operator >= c
用户输入一个数字( float 或整数),并且它必须大于下限。 这是从 UITextField 获取数字的代码: NSNumberFormatter * f = [[NSNumberFormatter
我已经摆弄这段代码大约一个小时了,它让我难以置信。我认为解决方案相当简单,但我似乎无法弄清楚。无论如何,这里去。我制作了一个 javascript 函数来检查用户输入的字符,以便它只能接受 7 个字符
我不太明白为什么当我们在不覆盖 equals 的情况下比较具有相同类属性的两个实例时方法,它将给出 false .但它会给出 true当我们比较一个案例类的两个实例时。例如 class A(val
我是一名优秀的程序员,十分优秀!