剑指Offer的学习笔记(C#篇)-- 连续子数组的最大和
2024-09-08 01:05:07
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
一 . 题目分析
上述题目太过复杂,于是我将他变了一种问法:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
简而言之,数组嘛,分为完整数组和子数组,这个题目中将的是:如果我这个数组中存在负数,找出这个数组中最大的子数组。例如输入的数组为{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},因此输出为该子数组的和18。
做法:
二 . 代码实现
class Solution
{
public int FindGreatestSumOfSubArray(int[] array)
{
// write code here
//鲁棒判断
if (array.Length == )
return ;
//定义连加运算常数a和最大值常数max(用于最后输出)
int max = array[];
int a = ;
//循环遍历
for(int i = ;i<array.Length;i++)
{
//输入一个数组常数+a>这个输入的常数,加上他
if (array[i]+a>array[i])
{
a +=array[i];
}
//否则,把a等于他
else
{
a = array[i];
}
//最终输出判断
if(a>max)
{
max = a;
}
}
return max;
}
}
最新文章
- VC程序获取管理员权限
- js,jquery,css,html5特效
- subString(), subStr(),splice(),split()的区别
- Conway&#39;s Game of Life: An Exercise in WPF, MVVM and C#
- checkbox改成radio效果,单选,取消
- shell如何自动输入密码
- [AngularJS] Hijacking Existing HTML Attributes with Angular Directives
- java完整的代码执行过程 堆栈+方法区
- [改善Java代码]使用forName动态加载类文件
- (转)C# NameValueCollection集合
- 美化 input type=file控件
- Redis 提供的好的解决方案 实例
- 如何把函数都用promise方式实现?
- Windows环境下Android Studio安装和使用教程
- Database Design Guidelines
- 32.QT-制作最强电压电阻表盘,可以自定义阴影效果,渐变颜色,图标,文字标签等-附带demo程序
- var 全局变量 局部变量
- (转)MTU&;MSS
- C语言基础:结构体 分类: iOS学习 c语言基础 2015-06-10 21:47 28人阅读 评论(0) 收藏
- 使用RegSetValueEx修改注册表时遇到的问题(转)
热门文章
- Android 破解
- 使用expect实现shell自动交互
- NPM 与 Nodejs
- 解决/usr/bin/ld: cannot find -lmysqlclient错误
- EASYARM-IMX283 制作ubifs文件系统
- SETEVENT的使用
- 《java编程思想》:第五章,初始化与清理
- bootstrap框架日期时间 开始日期和结束日期选择
- 「LOJ#10042」「一本通 2.1 练习 8」收集雪花 (map
- ACM学习历程—HDU4725 The Shortest Path in Nya Graph(SPFA &;&; 优先队列)