首页 > 其他分享 >222

222

时间:2024-04-10 21:27:12浏览次数:8  
标签:arr int max sum Max include 222

题目:最大连续子数组和求解问题
一、背景:
问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20。
二、解题
代码如下:

include <stdio.h>

include <stdlib.h>

int main()
{
int* arr;
int N = 0, input = 0, i = 0;
int sum = 0, max = 0;
scanf_s("%d", &N);
arr = (int*)malloc(sizeof(int) * N);
int minus = 0;
//对数组进行赋初值,并且记录负数个数
for (i = 0; i < N; i++)
{
scanf_s("%d", &input);
arr[i] = input;
if (input < 0)
{
minus++;
}
}
//如果全为负数,直接输出0,并结束程序
if (minus == N)
{
printf("0");
return 0;
}
//对最大子数组进行求解
max = arr[1];
for (i = 0; i < N; i++)
{
sum = sum + arr[i];
if (sum > max)
{
max = sum;
}
if (sum < 0)
{
sum = 0;
}
}
printf("%d", max);
return 0;
}
三、测试
表1 判定/条件覆盖测试样例
测试样例 测试结果 说明
n=6,arr[6]={-2,11,-4,13,-5,-2} 20 正常情况最大子段和为20
n=5,
arr[5] = { -1,2,3,-6,7 } 7 结果为最大的一个正数
n=6, arr[6]={-2,-11,-4,-13,-5,-2} 0 数组中都是负数,所以为0
n=6, arr[6]={1,2,3,4,5,6} 21 结果中都是正数,结果为正数全部相加

测试代码如下:

include "stdafx.h"

include "CppUnitTest.h"

include "..\Max\标头.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace UnitTest1
{
TEST_CLASS(UnitTest1)
{
public:

    TEST_METHOD(TestMethod1)
    {
        int arr[6] = { -2,11,-4,13,-5,-2 }, max;
        max = Max(arr, 6);
        Assert::AreEqual(max, 20);
    }
    TEST_METHOD(TestMethod2)
    {
        int arr[5] = { -1,2,3,-6,7 }, max;
        max = Max(arr, 5);
        Assert::AreEqual(max, 7);
    }

    TEST_METHOD(TestMethod3)
    {
        int arr[6] = { -2,-11,-4,-13,-5,-2 }, max;
        max = Max(arr, 6);
        Assert::AreEqual(max, 0);
    }

    TEST_METHOD(TestMethod4)
    {
        int  arr[6] = { 1,2,3,4,5,6 }, max;
        max = Max(arr, 6);
        Assert::AreEqual(max, 21);
    }
};

}
测试运行结果如下图1所示:

图1 单元测试运行结果
四、总结:
通过本次实验,我仔细研究明白了子数组最大和的求法。而且深入的了解判定/条件的测试方法并进行了大量练习。通过这次实验,我已经可以熟练进行代码测试,对测试的思想以及测试工具都有了更深一步的掌握。我会在日后学习中大量练习这种测试方法,为我日后的工作学习做好准备。
五、博客地址
https://home.cnblogs.com/u/xuhl66
六、Github地址
https://github.com/xuhl66

请在作业最后部分填写如下表格记录本次工作详细信息
项目 记录结果
日期 2024.4.7
开始时间 2024.4.6
结束时间 2024.4.7
编码行数 91
错误数量 8

标签:arr,int,max,sum,Max,include,222
From: https://www.cnblogs.com/xuhl66/p/18127456

相关文章

  • LeetCode 2220.转换数字的最少位翻转次数
    一、题目二、知识点符号描述运算规则&与两位都为1结果为1|或两位都为0结果为0^异或两位相同为0不同为1~取反(非)0变1,1变0<<左移二进制位全部左移,高位丢弃,低位补0>>右移二进制位全部右移,低位丢弃,高位补符号位>>>无符号右移二进......
  • 16天【代码随想录算法训练营34期】第六章 二叉树part03(● 104.二叉树的最大深度 559
    104.二叉树的最大深度#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defmaxDepth(self,root:O......
  • 文件名按数字排序,可以排序多组数字,尤其是99-333~~_222这种复杂数字组合的文件名或字符
    这是我本人编写的一个排序算法,主要就是解决复杂多组数字组合的这种文件名或者字符串的排序,排序主要规则就是从前往后对每一组数据进行排序,效果及截图如下:以下是使用方法:第一步搜索和安装我的Nuget包搜索和安装zmjtool这个包,我写的,如下图:第二步使用HMSorter的Sort方法进行......
  • ssh -p 2222怎么进docker容器
    要通过SSH和端口2222进入Docker容器,您需要确保容器内已经安装并运行了SSH服务器,并且已经将宿主机的2222端口映射到容器的SSH端口(通常为22)。以下是一般的步骤:1、启动容器时映射端口:当您启动容器时,使用-p参数将宿主机的2222端口映射到容器的SSH端口。例如:dockerrun-d--n......
  • 蓝牙5.2低功耗芯片PHY6222,支持MESH组网,适用于灯控等智能领域
    目前,蓝牙技术已经被广泛应用于包括消费电子、汽车电子、医疗设备、智能家居甚至是工业领域在内的所有物联网智能产品中。蓝牙Mesh智能灯,只是智能家居设备的开始,采用蓝牙Mesh方案的智能家居设备,能够自动快速进行蓝牙配对和建立网络连线,加速布局智能家居生态系统。今天跟大家探讨一......
  • abc222D 夹在两升序数组之间的升序数组个数
    给定长度为n的两升序数组A[i]和B[i],其中A[i]<=A[i+1],B[i]<=B[i+1],并且0<=A[i]<=B[i]<=3000,找长度为n的数组C[i],满足A[i]<=C[i]<=B[i]。求满足该条件的C的个数,结果对998244353取余。1<=n<=3000设dp[i][j]表示前i个数以j结尾的方案数,那么$dp[i][j]=\sum_{k=0}^{j}dp[i-1][k]$,这......
  • 代码随想录 第十六天 | ● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树
    leetcode:104.二叉树的最大深度-力扣(LeetCode)思路:递归判断每次左右节点的是否存在,存在自然加一,return的1就是这样,判断子节点的左右两端是否有节点,统计有的节点数量,也就是左右的高度classSolution{publicintmaxDepth(TreeNoderoot){//后序遍历if......
  • AT_abc222_f [ABC222F] Expensive Expense 题解
    分析没脑子的题目。一眼换根DP。定义\(\mathit{f}_{i}\)表示\(i\)到\(i\)为根子树中某一个节点的距离最大值;\(\mathit{g}_{i}\)表示\(i\)经过其父节点到某个节点的距离最大值。那答案就是\(\max(\mathit{f}_i,\mathit{g}_i)\)。考虑转移。\(\mathit{f}_i\)的转移很......
  • 222. 完全二叉树的节点个数c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intcountNodes(structTreeNode*root){if(!root)return0;if(!root->left&&!root->......
  • 简单看下最近的Spring Secrurity、Spring漏洞(CVE-2024-22234、CVE-2024-22243)
    最近的这两个cve我看国内很多情报将其评为高危,所以想着去看看原理,看完发现都比较简单,利用要求的场景也相对有限(特别是第一个),所以就随便看下就行了SpringSecurity用户认证绕过(CVE-2024-22234)先看下官网的公告(https://spring.io/security/cve-2024-22234)InSpringSecurit......