1.原题链接https://leetcode.com/problems/maximum-subarray/discuss/2.题目要求给定一个整型数组，返回其子串之和的最大值例如，[-2,1,-3,4,-1,2,1,-5,4]中，[4,-1,2,1]可以构成最大子串之和63.解题思路对数组进行一次遍历，每次加入一个元素...

GoodSubarrays题意：找给定串中满足(sum_{i=l}^{r}a_{i}=left(r-l+1ight))的子串的个数题解：式子转换：(sum_{i=l}^{r}a_{i}=left(r-l+1ight))连边同时减去(left(r-l+1ight))得：(sum_{i=l}^{r}left(a_{i}-1...

整体上3个题都是求subarray，都是同一个思想，通过累加，然后判断和目标k值之间的关系，然后查看之前子数组的累加和。map的存储：560题是存储的当前的累加和与个数　　　　　　561题是存储的当前累加和的余数与第一次出现这个余数的位置　　　　　　325题存储的是当前累加和与第一次出现这个和的位置其实561与325都...

begin,end必须初始化，如果整个数组是排序好的，经过for循环后，begin、end还是原始的值。注意：end必须比begin小1，因为最终的长度是end-begin+1，关键在于这个+1的地方 classSolution{public:intfindUnsortedSubarray(vector<...

53.MaximumSubarray 之前的值小于0就不加了。dp[i]表示以i结尾当前的最大和，所以需要用一个变量保存最大值。动态规划的方法：classSolution{public:intmaxSubArray(vector<int>&nums){vector<int>dp...

 Givenanintegerarray nums,findthecontiguoussubarray (containingatleastonenumber)whichhasthelargestsumandreturnitssum.classSolution(object):defmax...

2020-02-18 20:57:58一、MaximumSubarray经典的动态规划问题。问题描述：问题求解：publicintmaxSubArray(int[]nums){intres=nums[0];intn=nums.length;int[]dp=newint[n];dp[0]=nums[0];for...

2020-02-11 12:01:21问题描述：问题求解：本题的难度个人感觉还是蛮大的，主要是不容易想到O(n)的解。对于...a,[b,...,c],d,...，如果我们将其中的[b,...,c]进行翻转。如果两线段有重复，必减小原先的值。如果两线段无重复，必增加原先的值，且diff为2*gap。可通过如下...

2020-02-03 20:43:46问题描述：问题求解：publicbooleancanTransform(Stringstart,Stringend){intn=start.length();List<int[]>s=newArrayList<>();List<int[]&g...

2018-10-0301:12:42问题描述：问题求解：本题本质上其实是一个preSum问题的变种，每次求preSum%k，并将之保存到map中，如果之后再次得到相同的余数，则表示这两者之间的和是k的整数倍。需要注意的有两点：1）map初始化的时候需要加入(0,-1)2）如果k==0，那么直接将sum加入到map中即可...

2018-09-2723:33:49问题描述：问题求解：方法一、DP(MLE)动态规划的想法应该是比较容易想到的解法了，因为非常的直观，但是本题的数据规模还是比较大的，如果直接使用动态规划，即使不MLE，也是肯定会在大规模的数据量上TLE的。publicintsumSubarrayMins(int[]A){intres...

2018-09-2319:05:20问题描述：问题求解：显然的是暴力的遍历所有的区间是不可取的，因为这样的时间复杂度为n^2级别的，对于规模在50000左右的输入会TLE。然而，最后的解答也可以看作是一个暴力求解，也就是用Set来保存以当前数为结尾的左右可能解，在下一轮中遍历上一轮的所有解并进行或操作。这里有个难以一下...

2018-09-0123:02:46问题求解：问题求解：最开始的时候，一眼看过去就是一条dp嘛，保存每个数字结尾的长度和，最后求和就好，至于长度如何求，本题中需要用滑动窗口来维护。很好的题目，将滑动窗口算法和动态规划巧妙的结合了起来。publicintnumSubarrayProductLessThanK(int[]n...

2018-07-0813:24:31一、525. ContiguousArray问题描述：问题求解：我们都知道对于subarray的问题，暴力求解的时间复杂度为O(n^2)，问题规模已经给出是50000量级，显然只能是O(n)，至多O(nlogn)的复杂度。本题使用DP和滑动数组都比较棘手，这才是最麻烦的地方...

Findthecontiguoussubarraywithinanarray(containingatleastonenumber)whichhasthelargestsum.Forexample,giventhearray[−2,1,−3,4,−1,2,1,−5,4],...