题目要求：这道题是最近面试某个互联网公司的时候遇到的。题目大概是：给定一个数组A[]={1,-5,-3,2,7,-8,4},求其中连续的几个数的最大的和是多少。
最开始的思路，是从第一个数开始，计算第一个数为开始位置到最后一个数过程中所有的子数组的和，然后在计算第二个数为开始位置到最后一个数过程中所有的子数组的和，……，直到计算最后一个数的和。这个过程一个嵌套的for循环语句就可以了。
因为这个方法的时间复杂度为O（N^2）,不是很理想，还有一种更省时的方法。
更省时的思路：利用DP的思想，在对每次循环进行求和时，如果前面的部分对后面是“负贡献”的话，我们就应该”舍弃”前面的部分，从当前位置作为子数组开始的位置。这样，只需要遍历这个数组一次就可以，时间复杂度减小至O（N）
零子数组：对于长度为N的数组，求连续子数组和和最接近0的值和子数组最大连续子数组：给定一个数组A，求A的连续子数组...
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。...
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。...
题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。...
题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。...
题目： 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值...
要求：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。...
题目： 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值...
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 动态...
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求...
本文标题：【算法】-求一个数组的最大连续数组的值
本文链接：https://www.haomeiwen.com/subject/moduottx.html
网友评论