本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6025. 股票买卖 - AcWing题库【题目描述】最近越来越多的人都投身股市阿福也有点心动了。谨记着“股市有风险入市需谨慎”阿福决定先来研究一下简化版的股票买卖问题。假设阿福已经准确预测出了某只股票在未来 天的价格他希望买卖两次使得获得的利润最高。为了计算简单起见利润的计算方式为卖出的价格减去买入的价格。同一天可以进行多次买卖。但是在第一次买入之后必须要先卖出然后才可以第二次买入。现在阿福想知道他最多可以获得多少利润。【输入】输入的第一行是一个整数T TT表示一共有T TT组数据。接下来的每组数据第一行是一个整数N NN表示一共有N NN天。第二行是N NN个被空格分开的整数表示每天该股票的价格。该股票每天的价格的绝对值均不会超过1 , 000 , 000 1,000,0001,000,000。【输出】对于每组数据输出一行。该行包含一个整数表示阿福能够获得的最大的利润。【输入样例】3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2【输出样例】28 2 0【算法标签】#线性DP-一维#【代码详解】#includebits/stdc.husingnamespacestd;#defineN100005#defineINF0x3f3f3f3fintt,n,ans;// t: 测试用例数, n: 数组长度, ans: 最终答案inta[N];// 原始数组intde[N],db[N];// de[i]: 以a[i]结尾的最大区间差值, db[i]: 以a[i]开始的最大区间差值intdpe[N],dpb[N];// dpe[i]: 前i个元素的最大区间差值, dpb[i]: 从i到n的最大区间差值intmain(){intmn,mx;// 最小值, 最大值scanf(%d,t);// 输入测试用例数while(t--)// 处理每个测试用例{// 初始化dp数组memset(dpe,0,sizeof(dpe));memset(dpb,0,sizeof(dpb));scanf(%d,n);// 输入数组长度// 输入数组元素for(inti1;in;i){scanf(%d,a[i]);}// 正向遍历计算以a[i]结尾的最大区间差值mna[1];// 初始化最小值为第一个元素for(inti1;in;i){mnmin(mn,a[i]);// 更新最小值de[i]a[i]-mn;// 以a[i]为结尾的所有区间中区间差值最大的区间的区间差值dpe[i]max(dpe[i-1],de[i]);// 前i个元素构成的所有区间中区间差值最大的区间的区间差值}// 反向遍历计算以a[i]开始的最大区间差值mxa[n];// 初始化最大值为最后一个元素for(intin;i1;--i){mxmax(mx,a[i]);// 更新最大值db[i]mx-a[i];// 以a[i]为起始的所有区间中区间差值最大的区间的区间差值dpb[i]max(dpb[i1],db[i]);// 从i到n个数字构成的所有区间中区间差值最大的区间的区间差值}ans-INF;// 初始化答案为负无穷表示原序列中不相交的两个区间的区间差值加和的最大值// 枚举分割点计算两个不相交区间的最大差值之和for(inti1;in;i)// i是分割点{ansmax(ans,dpe[i]dpb[i1]);// 左半部分最大差值 右半部分最大差值}printf(%d\n,ans);// 输出结果}return0;// 程序正常结束}【运行结果】3 7 5 14 -2 4 9 3 17 28 6 6 8 7 4 1 -2 2 4 18 9 5 2 0