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

忘是亡心i 2022-10-07 03:53 117阅读 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 条评论，117人围观）

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

相关阅读

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

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

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

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

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

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

相关 Python 实现最大子数组和算法

Python 实现最大子数组和算法最大子数组和问题是一个经典的动态规划问题，它的目标是在一个给定的数组中找到连续子数组的最大和。在本文中，我们将介绍如何使用 Python

系统管理员/ 2024年03月16日 21:53/ 0 赞/ 47 阅读

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

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

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

相关最大子数组和

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

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

相关最大子数组和

/ 输入一个整数数组nums，请你在其中找一个和最大的子数组，返回这个子数组的和 dp[i]表示以nums[i]的最大子数组和状态 / public c

青旅半醒/ 2022年10月27日 13:49/ 0 赞/ 164 阅读

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

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

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

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

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

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

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

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

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

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

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

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