-
极资源官方
- 热度7452℃
---答题基础知识储备---
动态规划：基本思想与“分治”思想类似，通过将待求解的问题拆分成若干子问题(阶段)，按顺序求解子阶段，前一子阶段的解，为后一子阶段的求解提供有用信息。
在求解任一子阶段问题时，列出各种可能的局部解，通过决策，保留最有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划算法与分治算法的区别：动态规划法分解后得到的子问题，往往不是相互独立的，下一阶段的解一般建立在上一阶段的解之上，进行进一步求解。
------
题目：
输入一个整型数组，数组里有正数也有负数。将数组中连续的一个或多个整数组成一个子数组，每个子数组有一个和。求所有可能组成的子数组中，和的最大值，要求时间复杂度为O(n)。
例如：输入的整型数组为1,-2,3,10,-4,7,2,-5，那么这个整型数组中，和最大的子数组为3,10,-4,7,2，因此，输出该整型数组的最大和为18。
答题分析：
这道题，如果直接通过枚举的方式来实现：一个有n个元素的数组，其连续子序列数组的最多可能有n(n+1)/2个，将全部连续子序列枚举出来的算法复杂度为O(n^2)；然后，对一个长度为n的数组所有子序列数组元素求和的算法复杂度为O(n)，所以通过枚举方式实现总的算法复杂度为O(n^3)；不符合题目O(n)的要求。
在这里，我们可以使用动态规划的方式来实现：从左到右依次遍历数组元素，将元素递加求和，使用sum保存和值，使用max保存和的最大值，若出现sum<0，则将sum清零，重新开始递加。
解答：
代码实现：
1 2 3 4 5 6 7 8 9 10 | int maxSubarray(){ int arr[] = {1, -10, 20, 5, 7, -9, 13, -2, 30, 6, -7, 4}; int sum=0,max=0,len=12; for(int i=0;i<len;i++){ sum += arr[i]; max = MAX(sum,max); if(sum<0) sum=0; } return max;} |
需要注意的是：如果求解的整型数组中全是负数值，那么求和最大值应该数组的最大值，单独考虑计算。
友情提示：垃圾评论一律封号...