环状数组最大子串和 最大和最小是相对的
数组 最大 最小 子串 相对
2023-09-27 14:25:01 时间
要知道,最大和最小是相对的,用总和减去最小的就能得到最大的。 编程之美的题目没看懂,然后参考了http://zhangpeizhen.blog.163.com/blog/static/231873112201431784024921/
两种情况
1、普通数组,可以o(n)求最大子串和。
2、如果是环状,那么则要看到跨越 n-1 到 0 的这段环状的情况,要求这段最大的和,只需要用总和减去非环状的最小子串和即可。
然后取两种情况的最大值即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> using namespace std; void dp() { int i,t1,t2; t1 = arra[0]; t2 = arra[0]; Max = t1; Min = t2; for( i = 1 ; i < n ; i ++) { if(t1 <= 0) t1 = arra[i]; else t1 += arra[i]; if(t2 >= 0) t2 = arra[i]; else t2 += arra[i]; Max = max(t1,Max); Min = min(t2,Min); } Max = max(Max,total-Min); printf("%d\n",max(Max,0)); } int main() { while(~scanf("%d",&n)) { total = 0; for(int i = 0 ; i < n ; i ++) { scanf("%d",&arra[i]); total += arra[i]; } dp(); } return 0; }
但是我觉得少考虑了一种情况,比如全部为-1的数组,
普通数组最大子串和为-1,
按照上面求的最大的环状的必然为0,但是这样就是什么都不取的状态,
所以我觉得最后需要判断 是否 最小子串和 与 整个数组和 相等,如果相等说明就是上面考虑的情况,那么就取普通数组的的最大子串和就行了。
相关文章
- 最长无重复子数组
- NYOJ 745 首尾相连数组的最大子数组和
- 【Leetcode】53. 最大子数组和(简单)
- [算法]最大连续子数组和,最长重复子串,最长无重复字符子串
- 乘积最大子数组-python
- [nowCoder] 子数组最大乘积
- 数组-螺旋矩阵(java实现)
- 有关回旋数组的程序
- 数据结构 | 串的模式匹配 KMP算法 next数组
- js将数组分割成等长数组
- java字符串数组排序
- Java基础篇:数组
- LeetCode215之数组中的第K个最大元素(相关话题:堆排序,快速排序,减治法)
- 【刷题笔记】之牛客面试必刷TOP101(二分查找-I + 二维数组中的查找 + 寻找峰值 + 数组中的逆序对 + 旋转数组的最小数字 + 比较版本号)
- 第2章 数字之魅——子数组的最大乘积
- 《剑指offer》4:二维数组查找
- 求n以内最大的k个素数以及它们的和、数组元素循环右移问题、求最大值及其下标、将数组中的数逆序存放、矩阵运算
- [LeetCode] 1330. Reverse Subarray To Maximize Array Value 翻转子数组得到最大的数组值
- 【bzoj4785】[Zjoi2017]树状数组 线段树套线段树
- 互评作业:使用数组