【数据结构与算法面试题】子数组的最大和

忘是亡心i 2022-10-07 03:53 152阅读 0赞

> 题目来源“[数据结构与算法面试题80道][80]”。  
> ![这里写图片描述][946f781033f9454736251ff3d35f5223.png]

问题分析：在数组的每一个位置处保存当前的最大值，当前的最大值组成为：

f ( x i ) = \{ x i if i = 0    o r    f ( x i − 1 ) ⩽ 0 f ( x i − 1 ) + x i if f ( x i − 1 ) > 0 f\\left ( x\_i \\right )=\\begin\{cases\} x\_i & \\text\{ if \} i=0\\; or\\;f\\left ( x\_\{i-1\} \\right )\\leqslant 0 \\\\ f\\left ( x\_\{i-1\} \\right )+x\_i & \\text\{ if \} f\\left ( x\_\{i-1\} \\right )> 0 \\end\{cases\} f(xi)=\{ xif(xi−1)\+xi if i=0orf(xi−1)⩽0 if f(xi−1)>0

解决方案：

int get_max_subarray(int *a, int length, bool &is_array_ok){
    	if (NULL == a || length <= 0){
    		is_array_ok = false;
    		return 0;
    	}
    
    	int *p_h_a = (int *)malloc(sizeof(int) * length);
    	// 遍历数组
    	int max_num = 0;
    	for (int i = 0; i < length; i++){
    		if (i == 0 || (i > 0 && p_h_a[i-1] <= 0)){
    			p_h_a[i] = a[i];
    		}else{
    			p_h_a[i] = p_h_a[i-1] + a[i];
    		}
    		if (max_num < p_h_a[i]) max_num = p_h_a[i];
    	}
    	free(p_h_a);
    	
    	is_array_ok = true;
    	return max_num;
    }

[80]: https://yq.aliyun.com/articles/40478?utm_content=m_15768
[946f781033f9454736251ff3d35f5223.png]: /images/20221005/b362b1bb471a491aa305ef2bceac054f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：连续子数组的最大和

![e9333cf73665af603403d93d5e00ea9f.jpeg][] 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

深藏阁楼爱情的钟/ 2024年04月01日 10:26/ 0 赞/ 75 阅读

相关【数据结构与算法之面试题】数组和字符串类面试题

【数据结构与算法之面试题】数组和字符串类面试题文章目录【数据结构与算法之面试题】数组和字符串类面试题 1 数

Love The Way You Lie/ 2024年03月25日 20:47/ 0 赞/ 55 阅读

相关【数据结构与算法】Kadane‘s算法（动态规划、最大子数组和）

文章目录一、算法原理二、例题 2.1 最大子数组和 2.2 环形子数组的最大和一、算法原理 `Kadane's`算法是

一时失言乱红尘/ 2024年02月18日 13:00/ 0 赞/ 25 阅读

相关面试热题（最大子数组和）

> 给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > > 子数组是数组中的一个连续部分。 > >

忘是亡心i/ 2023年10月14日 18:53/ 0 赞/ 32 阅读

相关算法-最大子数组和

文章目录 1. 最大子数组和问题 2. 解法 1. 最大子数组和问题给定一个整数数组 nums ，找出一个具有最大和的连续子数组（子数组最少包含一个

川长思鸟来/ 2023年10月01日 21:04/ 0 赞/ 18 阅读

相关最大子数组和

/ 输入一个整数数组nums，请在其中找一个和最大的子数组动态规划定义dp数组：dp[i]是以num[i]结尾的最大子数组和 / public cla

矫情吗；*/ 2022年10月29日 10:28/ 0 赞/ 206 阅读

相关【数据结构与算法面试题】子数组的最大和

> 题目来源“[数据结构与算法面试题80道][80]”。 > ![这里写图片描述][946f781033f9454736251ff3d35f5223.png] 问题分析：

忘是亡心i/ 2022年10月07日 03:53/ 0 赞/ 153 阅读

相关【面试题】连续子数组的最大和

题目有一个整型数组，里面的元素有正数和负数，一个或者连续的多个元素组成一个子数组，求所有子数组的和的最大值。也就是连续子数组最大和问题。分析这道题一般使用动

梦里梦外;/ 2022年08月09日 09:58/ 0 赞/ 138 阅读

相关面试题31：连续子数组的最大和

面试题31：连续子数组的最大和题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常

我会带着你远行/ 2022年07月12日 05:51/ 0 赞/ 135 阅读

相关力扣 (LeetCode)-最大子序和,JavaScript数据结构与算法（数组）

Github来源：力扣 (LeetCode)｜刷题打卡 | 求星星 ✨ | 给个❤️关注，❤️点赞，❤️鼓励一下作者 > \[已开启\]任务一：刷题打卡 \ 10 篇大家

浅浅的花香味﹌/ 2021年07月24日 11:30/ 0 赞/ 286 阅读