点击刷新
先给题
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
有三种算法，暴力破解、分治、还有线性，题目要求时间复杂度为O(n)，我们先抛开题目不谈，我们先谈一下这三种情况。
1.暴力破解（这个没啥可说的，直接上代码了）
maxarray findMaximumSubarrayBruteForce(int* a, int low, int high) { maxarray num; num.low = low, num.high = low, num.sum = a[low];//默认第一个是最大子数组 for (int i = low; i <= high; i++) { int sum = 0, left = i; for (int j = i; j <= high; j++) { sum += a[j]; if (sum > num.sum) { num.low = left; num.high = j; num.sum = sum; } } } return num; }
2.分治解法
（1）先说未优化的分治解法，分治其实就是分三种情况，
定一个mid值（选取数组中间），要么最大子数组全部在mid的左半部分，要么在右半部分，要么就是在mid附近（即既包含左半部分也包含右半部分）
代码如下：
struct maxarray { int low; int high; int sum; };
maxarray findMaxCrossingSubarray(int* a, int low, int mid, int high) { maxarray num; int leftsum = 0, rightsum = 0, sum = 0; for (int i = mid; i >= low; i--) { sum += a[i]; if (sum > leftsum) { leftsum = sum; num.low = i; } } sum = 0; for (int i = mid + 1; i <= high; i++) { sum += a[i]; if (sum > rightsum) { rightsum = sum; num.high = i; } } num.sum = leftsum + rightsum; return num; }
maxarray findMaximumSubarray(int* a, int low, int high) { if (high == low) { maxarray num; num.low = low; num.high = high; num.sum = a[low]; return num; } else { int mid = (high + low) / 2; maxarray leftnum = findMaximumSubarray(a, low, mid); maxarray rightnum = findMaximumSubarray(a, mid + 1, high); maxarray crossingnum = findMaxCrossingSubarray(a, low, mid, high); if (leftnum.sum >= rightnum.sum && leftnum.sum >= crossingnum.sum) return leftnum; else if (rightnum.sum >= leftnum.sum && rightnum.sum >= crossingnum.sum) return rightnum; else return crossingnum; } }
以上代码是求最大子数组和的问题，那么如果要求子数组长度也是最大呢，像上部分代码，如果 输入 0 0 0 0 那么得到的结果 low = 1 high = 1 sum = 0（数组从1开始）
那么就要在上述判断中再判断high-low的大小 决定返回哪一个了（这里就不进行列举了）
（2）根据算法导论的思考题，我们可以对这个算法进行一些优化，当n小于某个值时，暴力破解的效率会更高一些
我们先来计算一下暴力破解和分治所需要的时间（由于时间太短，所以要用到毫秒来计算）
计算毫秒是https://www.cnblogs.com/xkfz007/archive/2011/11/14/2248394.html从这里摘取的（哎，我太菜了）
int test(int* a, int length) { TIMEB ts1, ts2; TIME_T t1, t2; ftime(&ts1); maxarray ab = findMaximumSubarrayBruteForce(a, 1, length); ftime(&ts2); cout << ab.low << " " << ab.high << " " << ab.sum << endl; t1 = (TIME_T)ts1.time * 1000 + ts1.millitm; t2 = (TIME_T)ts2.time * 1000 + ts2.millitm; printf("The difference is: %I64d seconds\n", t2 - t1); ftime(&ts1); maxarray aa = findMaximumSubarray(a, 1, length); ftime(&ts2); cout << aa.low << " " << aa.high << " " << aa.sum << endl; t1 = (TIME_T)ts1.time * 1000 + ts1.millitm; t2 = (TIME_T)ts2.time * 1000 + ts2.millitm; printf("The difference is: %I64d seconds\n", t2 - t1); return 1; }
这是运行结果的测试，利用rand随机生成的数，输入的是n值，我们发现当n到达400时，才有了时差，所以很难在这上面解决时间问题。
我从https://blog.csdn.net/zxhio/article/details/82290307?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control这篇文章中得知了在10以内 效率是暴力快，
所以改良将high==low 的判断改为 high-low<10 利用暴力破解即可，这便是改良后的分治算法。
3.最后到线性解法了
已知[1..j]的最大子数组，计算[1..j+1]最大子数组的思路：[1..j+1]的最大子数组要么是[1..j]的最大子数组，要么是某个子数组[i..j+1] (1 <= i <= j+1 )。
为了方便理解这句话，我们先来举个例子
首先我们默认数组第一位是最大数组，也就是[1,1]是最大的子数组，那么[1,2]的最大子数组有几种情况呢？[1,1]也就是我们已经记录的最大子数组maxsum。[2]或者[1,2]这三种情况，而[2]和[1,2]就是上述中的[i..j+1] (1 <= i <= j+1 )，也就是说如果[1,2]的值>[2]，那么[2]就肯定不是最大子数组，i = 1，去比较maxsum和[1,2],如果[1,2]的值<[2],那么我们重置目前的sum值，也就是重置i的值（sum是[i，j+1]的最大子数组和），让[2]的值和maxsum去比较。
也就是说我们先找到[i..j+1]的最大子数组 ，再拿这个子数组与maxsum去比较。
同理，当求[1,3]时，我们已经知道了[1,2]的最大子数组，那么情况就分为四种了[1,2]的最大子数组，[3]或者[1,3]或者[2,3],后面的都属于[i,3]。而i=1还是i=2都是由前面决定的（如果1 2的值小于 2 那么 1 2 3的值肯定小于 2 3，前面的操作已经帮助我们确定了i的值，接下来判断[i,3]与[3]的关系，来决定i是继续原来的值，还是变为3,这样也就比较出了后三者哪个是最大的了）。接下来再与maxsum比较即可。
当j的值逐渐增加是道理都与[1,3]的操作相同。
好，理解了原理，我们就可以写代码了。
maxarray findMaximumSubarrayLinear(int* a, int low, int high) { maxarray num; num.low = low, num.high = low, num.sum = a[low];//默认第一个是最大子数组 int sum = a[low], left = low; for (int i = low + 1; i <= high; i++) { if (sum + a[i] > a[i]) sum += a[i]; else { sum = a[i]; left = i; } if (sum > num.sum) { num.low = left; num.high = i; num.sum = sum; } } return num; }
class Solution { public: int maxSubArray(vector<int>& nums) { int sum = nums[0], maxsum = nums[0]; for (int i = 1; i < nums.size(); i++) { if (sum + nums[i] > nums[i]) sum += nums[i]; else sum = nums[i]; if (sum > maxsum) maxsum = sum; } return maxsum; } };
© 著作权归作者所有
相关热门文章
发表评论
