LeetCode实战：最大子序和
题目英文
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
题目中文
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2:
输入: [-2,1],
输出: 1
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
算法实现
利用暴力算法：
public class Solution {public int MaxSubArray(int[] nums) {int len = nums.Length;if (len == 0)return 0;if (len == 1)return nums[0];int max = int.MinValue;for (int i = 0; i < len; i++){int sum = nums[i];if (sum > max){max = sum;}for (int j = i + 1; j < len; j++){sum += nums[j];if (sum > max){max = sum;}}}return max; }
}
利用动态规划：
动态规划的最优子结构如下：
max[i] = Max(max[i-1] + nums[i], nums[i])
public class Solution {public int MaxSubArray(int[] nums) {int len = nums.Length;if (len == 0)return 0;if (len == 1)return nums[0];int[] max = new int[len];max[0] = nums[0];int result = max[0];for (int i = 1; i < len; i++){if (max[i - 1] + nums[i] > nums[i])max[i] = max[i - 1] + nums[i];elsemax[i] = nums[i];if (max[i] > result){result = max[i];}}return result; }
}
实验结果
利用暴力算法：
- 状态：通过
- 202 / 202 个通过测试用例
- 执行用时: 596 ms, 在所有 C# 提交中击败了 14.18% 的用户
- 内存消耗: 24.5 MB, 在所有 C# 提交中击败了 5.88% 的用户
利用动态规划：
- 状态：通过
- 202 / 202 个通过测试用例
- 执行用时: 136 ms, 在所有 C# 提交中击败了 91.85% 的用户
- 内存消耗: 24.4 MB, 在所有 C# 提交中击败了 5.88% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
- LeetCode实战：字符串相加
- LeetCode实战：字符串相乘
7. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
8. “哈希”类算法
- LeetCode实战：两数之和
9. “搜索”类算法
- LeetCode实战：搜索二维矩阵
10. “动态规划”类算法
- LeetCode实战：最长回文子串
11. “回溯”类算法
- LeetCode实战：全排列
11. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
PHP如何更好的利用PHPstorm的自动提示
说明 写了一段时间的java之后，特别不习惯PHP本身的弱类型方式，在写代码的时候总觉得不怎么放心，特别本身PHP又是弱类型的语言，所以在编码的时候，很多时候是没有代码提示的。 一个一般例子 class Data {public $name;pu…
2021年Java面试题目最新总结【90%面试会踩的坑】
学会java技术之后大家面临的最多的问题就是面试这关，求职面试java岗位是否能够成功是直接影响我们的工作机会的，所以对于Java程序员面试你准备好了吗?今天小编汇总了一下关于Java程序员面试，90%会踩到的坑。 2021年Java面试题目最新总结【90…
LeetCode实战：螺旋矩阵
题目英文 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1: Input: [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]Example 2: Input: [[1, 2, 3, 4],[5, 6, 7, 8],[9,10,11,…
Json的序列化和反序列化
1、引用命名空间: usingSystem.Runtime.Serialization;2、json的序列化和反序列化的方法： publicclassJsonHelper {///<summary>///序列化///</summary>///<typeparam name"T"></typeparam>///<param name"t">&l…
Angular开山篇
1：环境搭建 今天给大家介绍4种环境搭建的方法。一：Angular-cli的安装 官方指导文档：www.angular.cn/guide/quickstart 请使用cnpm来安装，或者配置淘宝镜像。 使用原生npm安装可能会遇到的问题： 需要python的环境可能会…
零基础参加软件测试培训需要学多长时间
软件测试对于零基础学员来说是非常好入门的，软件测试没有很多的限制，那么零基础参加软件测试培训需要学多长时间呢?来看看下面的详细介绍吧。 零基础参加软件测试培训需要学多长时间?软件测试培训时间一般都在四个月左右，四个月时间的课程内…
Windows API函数大全
1. API之网络函数 WNetAddConnection 创建同一个网络资源的永久性连接 WNetAddConnection2 创建同一个网络资源的连接 WNetAddConnection3 创建同一个网络资源的连接 WNetCancelConnection 结束一个网络连接 WNetCancelConnection2 结束一个网络连接 WNetCloseEnum 结束一…
LeetCode实战：螺旋矩阵 II
题目英文 Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order. Example: Input: 3 Output: [[ 1, 2, 3 ],[ 8, 9, 4 ],[ 7, 6, 5 ] ]题目中文 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素&#x…
电子文件归档为什么非云不可
本文讲的是电子文件归档为什么非云不可华为云为企业搭建功能强大的电子文件归档系统平台，一站式满足文件存储与管理、协同分享、移动办公等不同的业务需求。打造安全、高效、便捷的文件归档环境，帮助企业节省运营成本，优化管理流程࿰…
北京学习Java培训有哪些比较好
北上广算是互联网技术大咖的聚集之地，很多知名互联网企业都在这些城市，随之java培训机构也是非常多的，那么在北京学习java培训有哪些比较好呢?来看看下面的详细介绍吧。 北京学习Java培训有哪些比较好?想要在这些培训机构中选择比较靠谱的J…
C#命名规则、开发习惯和风格
1. 文件命名组织 1-1文件命名 1. 文件名遵从Pascal命名法，无特殊情况，扩展名小写。 2. 使用统一而又通用的文件扩展名： C# 类 .cs 1-2文件注释 1. 在每个文件头必须包含以下注释说明 1 在每个文件头必须包含以下注…
LeetCode实战：不同路径
题目英文 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Fini…
前端部分面试题整理，欢迎补充
1.ng中如何配置路由，$scope和$rootscope的原理ng中如何配置路由?1)使用内置路由模块ng-routevar app angular.module(ngRouteExample, [ngRoute]).controller(MainController, function($scope) {}).config(function($routeProvider, $locationProvider) {$routeP…
JS栈结构的简单封装
栈：是一种遵循后进先出(Last In First Out / LIFO) 原则的一种有序集合。 新添加或者要删除的元素都会保存在栈的同一端，我们把它叫做栈顶，另外一端叫做栈底。 在栈中所有的新元素都接近栈顶，而所有的旧元素都接近栈底。 在我们的…
记录CSS3 target伪类简介
CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元…
LeetCode实战：合并两个有序数组
题目英文 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively.You may assume that nums1 has enough space (size that is greater o…
Java云托管服务的开支削减策略
\摘要\随着项目不断扩大，你需要将其迁移到更大的虚拟机上。但如果新虚拟机环境超出了你的需求则会产生额外开支。\相比虚拟机，容器具有更小的粒度，并且无需重启运行中的实例即可垂直扩展。\单体应用和历史遗留应用无需更改配置，即…
SpringBoot培训教程--史前文明之Spring简介
一. Spring之起源 1.你知道J2EE吗? 要说到Spring的历史起源，首先咱们要说说J2EE这个玩意儿。 J2EE在1999年和2000年的时候开始得到广泛实现，在J2EE中提出了”事务管理“等核心中间层标准化的概念，但是在实践中出现了各种问题，尤其…
利用外部命令Oralce数据库导入导出
1--数据库导出(exp) 首先进入命令行 导出数据库 在命令行中输入如下命令: exp c2j/c2jc2j filec:/table.dmp tablesjbitaku,jbitakum grantsy 然后按回车键 说明: c2j/c2jc2j 分别表示用户名，密码和服务名 file：输出文件的位置和文…
LeetCode实战：子集
题目英文 Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums [1,2,3] Output: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ]题目中文 给定一组…
linux的挂载命令
在linux中所有的存储设备都必须挂载后才能使用，相当于windows的分配盘符 挂载命令 mount #查看系统中已经挂载好的设备 mount -a #根据/etc/fstab中的内容，自动挂载 /etc/fstab是系统开机的自动挂载文件 系统挂载时要自动检车测这个文件，如果…
软件测试需要学习什么技术
软件测试在近几年被很多企业都重视起来，互联网时代，APP种类越来越多，软件测试这一行业的发展前景是非常大的，那么想要学习软件测试需要学习什么技术呢?来看看下面的详细介绍。 软件测试需要学习什么技术? 每个软件在上线之前都离…
silverlight4.0 写文件不能设置默认文件名
Silverlight4.0 不提供SaveFileDialog的SafeFileName的写属性 Weve not exposed the "DefaultFileName" property on SaveFileDialog due to time constraints.Moe Elshall | Silverlight Development TeamMicrosoft Corporation等待5.0解决问题。转载于:https://www…
我是如何组织“算法刻意练习活动”的？
背景 在上个学期末，我们组织了一次团队的招新活动 – 如何加入 LSGO 软件技术团队？。 我们让预加入团队的同学在假期中完成以下两个任务之一： 学习 C# 语言： https://www.bilibili.com/video/av2357992/?p1学习 Python 语言&a…
[Ubuntu] ubuntu10.04系统维护之Wine的安装
在介绍安装wine之前，我想是有必要先介绍一下Wine的。当然，如果是Liunx的高手，我想是没必要看的，但是对于笔者这样的菜鸟级人物还是需要看一下的。 Wine是一款Liunx下的模拟器软件，但是Wine又不仅仅是一个模拟器软件&am…
Python培训教程：Python内置数据结构之双向队列
经常听说Python就是一门执行速度低的语言，可能是你的程序中使用了复杂的算法与数据结构，才会导致程序执行速率低的。在Python的标准库中提供了常见的数据结构工开发者使用，不仅执行速率比较快，还可以简化开发者的编程工作。下面我…
华为hybrid-vlan
华为hybrid-vlan、三层交换、DHCP拓扑：需求：1.路由器终结vlan2.交换机间以hybrid方式透传vlan3.PC以DHCP获取IP思路：1.PC的网关在路由器上2.配置hybrid-vlan3.配置DHCP步骤：路由器AR1：<Huawei>sy[Huawei]vlan 10…
android 按住拖动gallery防止马上加载数据导致gallery卡的方法
gallery菜单滑动有一个不好的效果就是每次经过中间的菜单都默认是被选中状态，同时会加载数据 以至于切换不流畅，有一种卡卡的感觉！！其实用线程来处理这个问题，一定的时间后如果选择的index值不变，说明已经稳…
LeetCode实战：买卖股票的最佳时机
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Say you have an array for which the ith element is the price of a given stock on day …
HTML5培训教程：HTML5基础介绍
HTML5发展史： HTML5草案的前身名为 Web Applications 1.0，于2004年被WHATWG提出，于2007年被W3C接纳，并成立了新的 HTML 工作团队。 • HTML 5 的第一份正式草案已于2008年1月22日公布。HTML5 仍处于完善之中。然而，大部…