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

news/2025/2/19 3:59:23/

 目录链接:

力扣编程题-解法汇总_分享+记录-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…