`
moxiaomomo
  • 浏览: 45689 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

关于求子数组的最大和

阅读更多
这道题实在是很经典的面试题。
题目主要是要求尽可能的减少时间复杂度。
个人也写了一下,方便以后回头温习。

int  getMaxVal(int a[],int n)
{
	int max=a[0]; //用来记录已经计算过的子数组的最大和
      int result=a[0];     //返回最终的子数组最大和
	for(int i=1;i<n;++i)
	{
		if(max>0)        
		{
			max+=a[i];
		}
		else max=a[i];

		if(max>result)
		{result=max;}
	}

	return result;
}
1
3
分享到:
评论

相关推荐

    求子数组最大和

    在编程领域,"求子数组最大和"是一个经典的算法问题,常见于计算机科学的数据结构与算法课程中。这个问题的目标是给定一个整数数组,找出这个数组中的一个连续子数组,使得其元素之和最大。这个问题的一个著名解决...

    C语言程序:求子数组的最大和

    求子数组的最大和 题目: 输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -...

    Java实现求子数组和的最大值算法示例

    "Java实现求子数组和的最大值算法示例" 本文主要介绍了Java实现求子数组和的最大值算法,涉及Java数组遍历、判断、运算等相关操作技巧。下面是对该算法的详细讲解和分析。 首先,需要了解子数组的概念。子数组是...

    求子数组最大和的解决方法详解

    【标题】:"求子数组最大和的解决方法详解" 【描述】:"本文深入探讨了求解子数组最大和的有效算法,适合需要了解此问题解决方案的人参考" 【标签】:"求子数组的最大和" 在计算机科学中,求子数组最大和是一个...

    求子数组最大和的实例代码

    总结来说,求子数组最大和的问题可以通过动态规划的Kadane算法在O(n)的时间复杂度内解决。实例代码展示了如何实现这个算法,通过比较当前元素与前一个子数组和,找出能够构成更大和的策略,并在遍历过程中保持最大子...

    PHP实现求连续子数组最大和问题2种解决方法

    关于连续子数组最大和这个问题,有两种解法,一种是动态规划 解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0]; for($i = 1; $i &lt; count($arr); $i++){ if

    求一组数组的两个最大值和两个最小值 分治法

    3. **求子数组的最大值与最小值**: - 对于每个子数组 `C1` 和 `C2`,分别找出两个最大值和两个最小值。这里可以通过排序子数组来实现。排序后,数组的第一个元素是最小值,最后一个元素是最大值。 4. **合并结果**...

    求子集c++算法,经典

    ### 求子集C++算法详解 #### 一、问题背景与定义 在计算机科学领域,求子集问题是常见的组合数学问题之一。对于给定的一组元素集合,我们需要找到该集合...希望本文能帮助读者更好地理解和掌握求子集问题的相关知识。

    Google微软-华为腾讯-面试笔试数据结构和算法编程题目和部分答案

    这其中包括了二元查找树转换为排序双向链表、设计包含min函数的栈、求子数组的最大和、在二元树中找出和为某一值的所有路径、查找最小的k个元素等题目。这些题目都是常见的数据结构和算法面试题目,旨在考察面试者的...

    [汇总II][最新整理]微软等公司数据结构%2B算法面试100题[第1-80题].pdf

    3. **求子数组最大和** 这是著名的“Kadane's Algorithm”。算法的核心思想是动态规划,通过遍历数组一次,维护当前子数组的最大和以及全局最大和。如果当前元素大于当前子数组的和加上当前元素,那么更新子数组的...

    几个经典算法源代码文件

    求子数组和的最大值 power函数的实现 10次90环的组合数 有两个整形数组,交换两个数组的元素使得两个元素和的差最小 打印幻方 走方格 求数对之差最大值 现有整型数组{1,2,4,3,5,8},写出一个函数,找出...

    July整理的100题微软数据结构和算法面试题

    3. **求子数组最大和**: 使用Kadane's算法,遍历数组一次,同时维护当前子数组的和与最大子数组的和。如果当前元素比前一个元素大,就累加;否则,重新从当前元素开始计算子数组的和。 4. **二元树找和为特定值的...

    前缀和详解21.zip

    2. **求子数组最大/最小值**:通过两次遍历数组,一次计算前缀和,一次计算后缀和,可以找到数组中的最大连续子数组和或最小连续子数组和,如Kadane's algorithm。 3. **异或操作**:数组元素的异或运算也满足前缀和...

    算法面试题总结_嵌入式-常用知识&面试题库_大厂面试真题.doc

    本资源摘要信息涵盖了各种算法面试题,包括二元查找树、二元树、栈、子数组最大和、二元树路径、最小k个元素、腾讯面试题、链表相交、怪题等多个方面的知识点。 1. 把二元查找树转变成排序的双向链表:本题目考察了...

    各大公司算法面试题

    - 对于求子数组的最大和问题,我们可以使用动态规划的思想,定义一个状态`dp[i]`表示以第`i`个元素结尾的子数组的最大和。对于每一个`i`,`dp[i]`的值可以通过前一个状态`dp[i-1]`来计算,即`dp[i] = max(dp[i-1]+...

    微软等公司数据结构-算法面试第1-100题汇总

    3. **求子数组最大和**: - 这是一个经典的Kadane's Algorithm问题,通过动态规划找到连续子数组的最大和。 - 遍历数组,每次比较当前元素与当前子数组和(初始化为负无穷大)和上一子数组和加上当前元素,取较大...

    (完整版)数据结构与算法面试题80道.docx

    3. **求子数组最大和**: 这是经典的Kadane's Algorithm问题,用于找到数组中连续子数组的最大和。遍历数组,保持当前子数组的和(初始化为负无穷大)和全局最大和。如果当前元素大于当前子数组的和加上当前元素,...

    程序员面试题精选100例

    根据提供的信息,我们可以总结出两个主要的编程面试题目及其解决方案,分别是求子数组的最大和以及查找最小的k个元素。 ### 1. 求子数组的最大和 #### 题目描述 输入一个整型数组,数组里包含正数和负数。要求找出...

Global site tag (gtag.js) - Google Analytics