​LeetCode解法汇总1186. 删除一次得到子数组最大和

news/2024/2/28 1:32:32

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦),(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最大的。

注意,删除一个元素后,子数组 不能为空

示例 1:

输入:arr = [1,-2,0,3]
输出:4
解释:我们可以选出 [1, -2, 0, 3],然后删掉 -2,这样得到 [1, 0, 3],和最大。

示例 2:

输入:arr = [1,-2,-2,3]
输出:3
解释:我们直接选出 [3],这就是最大和。

示例 3:

输入:arr = [-1,-1,-1,-1]
输出:-1
解释:最后得到的子数组不能为空,所以我们不能选择 [-1] 并从中删去 -1 来得到 0。我们应该直接选择 [-1],或者选择 [-1, -1] 再从中删去一个 -1。

提示:

  • 1 <= arr.length <= 105
  • -104 <= arr[i] <= 104

解题思路:

* 解题思路:

* 这题看题解的。核心就是动态规划:

* 分别构造两个数组,

* 数组1:一个都不减时,最大的连续数组之和

* 数组2:减1个时,最大的连续数组之和

 

代码:

class Solution1186
{
public:int maximumSum(vector<int> &arr){int length = arr.size();// 不删时,最大连续和vector<int> prefixSum0(length + 1);// 删1个时,最大连续和vector<int> prefixSum1(length + 1);prefixSum0[0] = arr[0];prefixSum1[0] = 0;int abs = prefixSum0[0];for (int i = 1; i < length; i++){prefixSum0[i] = prefixSum0[i - 1] <= 0 ? arr[i] : prefixSum0[i - 1] + arr[i];prefixSum1[i] = prefixSum0[i - 1] > prefixSum1[i - 1] + arr[i] ? prefixSum0[i - 1] : prefixSum1[i - 1] + arr[i];int max = prefixSum0[i] > prefixSum1[i] ? prefixSum0[i] : prefixSum1[i];abs = max > abs ? max : abs;}return abs;}
};


http://www.ppmy.cn/news/721468.html

相关文章

【Spring Boot】Spring Boot配置文件详情

前言 Spring Boot是一个开源的Java框架&#xff0c;用于快速构建应用程序和微服务。它基于Spring Framework&#xff0c;通过自动化配置和约定优于配置的方式&#xff0c;使开发人员可以更快地启动和运行应用程序。Spring Boot提供了许多开箱即用的功能和插件&#xff0c;包括嵌…

Sklearn实现泰坦尼克存活率预测

实例目标&#xff1a;实现泰坦尼克存活预测 处理步骤&#xff1a; 输入数据&#xff1a;使用Pandas读取训练数据(历史数据&#xff0c;特点是已经知道了这个人最后有没有活下来)训练模型&#xff1a;使用Sklearn训练模型使用模型&#xff1a;对于一个新的不知道存活的人&…

泰坦尼克训练数据集

链接&#xff1a;https://pan.baidu.com/s/175zFJE1NS2QoSP8P1omo_g 提取码&#xff1a;t1k8 代码如下&#xff1a;注意要修改文件路径哦 # 1、查看训练集数据情况 import pandas as pddata_train pd.read_csv("E:\\Desktop\\train.csv") print(data_train.shape) …

kaggle入门-泰坦尼克之灾

kaggle入门-泰坦尼克之灾 引言数据认识总结 特征处理建模预测logistic分类模型随机森林SVMxgboost 模型验证交叉验证学习曲线高偏差&#xff1a;高方差 模型融合总结后记 引言 一直久闻kaggle大名&#xff0c;自己也陆陆续续学了一些机器学习方面的知识&#xff0c;想在kaggle…

kaggle 泰坦尼克 高分 预测

kaggle 泰坦尼克 高分 预测 目录 kaggle 泰坦尼克 高分 预测1.前言2.包及数据导入3.数据的初步认识4.数据关系的可视化5.数据清洗与缺失值处理6.数据的统计分析7.超参数优化8.模型训练及结果输出9.总结10.贡献者介绍 1.前言 在第一篇文章中我们简单介绍了一下泰坦尼克号数据如何…

关于泰坦尼克之灾的数据分析

目录&#xff1a; 加载数据&#xff0c;分析数据数据清洗特征工程模型预测 1. 加载数据&#xff0c;分析数据的组成 import warnings warnings.filterwarnings("ignore")import re import numpy as np import pandas as pd import matplotlib.pyplot as plt impor…

kaggle泰坦尼克

Kaggle泰坦尼克预测(完整分析) 2017年06月26日 15:53:26 阅读数&#xff1a;10313 1.引言 先说一句&#xff0c;年末双十一什么的一来&#xff0c;真是非(mang)常(cheng)欢(gou)乐(le)&#xff01;然后push自己抽出时间来写这篇blog的原因也非常简单&#xff1a; 写完前两篇逻辑…

泰坦尼克数据分析与预处理

泰坦尼克数据分析与预处理 数据预览 import pandas import numpy as np from pandas import Series,DataFrame import matplotlib.pyplot as plt #from __future__ import division from scipy import stats import seaborn as sns ###首先导入各种模块 ###让图片在ipython no…

超级计算机泰坦 amd,基于AMD技术的泰坦超算宣告退役 推土机CPU最后的遗产

访问购买页面: 在中国的天河2号、神威太湖之光称霸10届TOP500超算之前&#xff0c;ORNL实验室的泰坦超算是世界第一&#xff0c;它也是最早的性能达到亿亿次的超算之一&#xff0c;为此泰坦超算使用了革命性的CPUGPU异构体系&#xff0c;处理器是AMD的皓龙6274 16核&#xff0c…

kaggle 泰坦尼克

#coding:utf-8 import matplotlib.pyplot as plt plt.rcParams[font.sans-serif][SimHei] #用来正常显示中文标签 plt.rcParams[axes.unicode_minus]False #用来正常显示负号 import pandas as pd # 数据分析 import numpy as np # 科学计算 from pandas import Series, Data…

超级计算机泰坦 amd,再见推土机:搭载AMD皓龙处理器的泰坦超算退役

原标题&#xff1a;再见推土机&#xff1a;搭载AMD皓龙处理器的泰坦超算退役 IT之家7月2日消息 超级计算机TOP500榜单中的绝大多数超算都搭载了Intel Xeon处理器&#xff0c;原因很简单&#xff0c;自从K10架构终结之后、ZEN架构推出之前的这段时间里&#xff0c;AMD一直都没有…

泰坦尼克分析

一、前言 最近在B站看到一博主在讲数据分析的课程&#xff0c;跟着看了几节课&#xff0c;每节课很短&#xff0c;很适合通勤充电。 前几天看了节泰坦尼克分析&#xff0c;觉得很有意思就敲了几行代码。 二、代码实现 1.数据处理 import pandas as pd import numpy as np #…

Kaggle 泰坦尼克

入门kaggle&#xff0c;开始机器学习应用之旅。 参看一些入门的博客&#xff0c;感觉pandas&#xff0c;sklearn需要熟练掌握&#xff0c;同时也学到了一些很有用的tricks&#xff0c;包括数据分析和机器学习的知识点。下面记录一些有趣的数据分析方法和一个自己撸的小程序。 1…

泰坦项目

import pandas as pd import numpy as np fileD:\新建文件夹 (6) data_trainpd.read_csv(file/titanic_train.csv) data_testpd.read_csv(file/titanic_test) import pandas as pd import numpy as np fileD:\新建文件夹 (6) data_trainpd.read_csv(file/titanic_train.csv) …

泰坦以太(第四稿)

泰坦以太(第四稿) titan_ysl 2019.11.20 从学习物理到现在,几十年来,我一直认为以太的存在能最合理地解释许多物理现象,但由于一直没人给于其适当的定义,导致其被废弃,从而让现代物理学出现了很多的无法理解的现象。前些年我一直在打工,也就没再关注这些事情,这几年自己…

lgb预测泰坦尼克

翻了一下csdn&#xff0c;发现没有用lgb模型处理泰坦尼克的&#xff0c;所以就去写了一下&#xff0c;代码里面注释点的部分是我为了解决报错的各种尝试&#xff0c;就不删除了&#xff0c;哈哈&#xff0c;代码拿走不谢 import numpy as np import pandas as pd import light…

泰坦尼克

1. 加载数据 import pandas as pd import numpy as np import matplotlib.pyplot as plt import seaborn as sns train_df pd.read_csv("tatannic/train.csv") test_df pd.read_csv("tatannic/test.csv")2. 特征类型分析 print(train_df.shape) train_…

建模之泰坦尼克生存预测

作者&#xff1a;北有鸣鹿 个人辛苦之作&#xff0c;请勿随意转载&#xff0c;必追究责任。如需转载&#xff0c;请联系我 #https://www.kaggle.com/c/titanic #本次建模的模型的最高准确率0.9665&#xff0c;AUC为0.9666 #1.导入数据集 import pandas as pd import numpy as …

Kaggle泰坦尼克之灾

逻辑回归应用之Kaggle泰坦尼克之灾 背景 训练和测试数据是一些乘客的个人信息以及存活状况&#xff0c;要尝试根据它生成合适的模型并预测其他人的存活状况。 1. 数据总览 train.csv和test.csv分别为训练集和测试集,ground_truth.csv为对应答案 得到这些后&#xff0c;对这…

windows下paddle安装,显卡是GTX titan X,已装最新驱动版本512.77,cuda版本11.6

按照paddle官网的教程安装paddle-gpu&#xff0c;即运行conda install paddlepaddle-gpu2.3.0 cudatoolkit11.2 -c https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/Paddle/ -c conda-forge &#xff0c;会报如下错误 即&#xff1a; CondaHTTPError: HTTP 000 CONNECTIO…
最新文章