大家好,我是毛毛。ヾ(´∀ ˋ)ノ
废话不多说开始今天的解题Day~
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
If you have figured out the O(n)
solution, try coding another solution using the divide and conquer approach, which is more subtle.
首先先简单的翻译一下题目
给定一个整数的阵列,从中找出总和最大的一个连续的子阵列(至少要有一个元素),并回传总和最大的值。
这个题目最暴力的情况就是用两个for loop去找最大总和,这样的时间复杂度会是O(n^2)
。目标就先放在写出O(n)
的演算法吧~
作法大致上是这样
[-2,1,4,3]
,实际来跑一次流程看看。-2
,currentSum则是代表每次子阵列的总和。class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSum = nums[0]
currentSum = 0
for num in nums:
if currentSum < 0:
currentSum = 0
currentSum += num
maxSum = max(maxSum, currentSum)
return maxSum
int maxSubArray(int* nums, int numsSize){
int maxSum = nums[0];
int currentSum = 0;
for (int i=0 ; i<numsSize ; i++){
if (currentSum < 0)
currentSum = 0;
currentSum += nums[i];
maxSum = (maxSum > currentSum? maxSum : currentSum);
}
return maxSum;
}
Python
C
大家明天见
<<: [Day07] Vue i18n - Datetime Formatting
>>: Day 22 : 模型优化 - 知识蒸馏 Knowledge Distillation
GOOGLE公云使用案例 大纲 Introduction(Global view) How to c...
终於倒数胜4天了!! 接续昨天的练习 1.在light comp加入一个Solid Composit...
Subscriber 与Publisher 相对应,是观察者模式中的Observer,Publish...
奄奄一息的山姆躺在地上,脑海中浮现了人生跑马灯。 「我为什麽会在这里?我的梦想,终究只是梦想吧.....
更多的设计参考 今天能花在Dungeon的时间一样很少,没有办法进行程序端的调整。只好再花些时间来看...