先给题
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
有三种算法,暴力破解、分治、还有线性,题目要求时间复杂度为O(n),我们先抛开题目不谈,我们先谈一下这三种情况。
//暴力破解法
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;
}
定一个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的大小 决定返回哪一个了(这里就不进行列举了)
我们先来计算一下暴力破解和分治所需要的时间(由于时间太短,所以要用到毫秒来计算)
计算毫秒是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 利用暴力破解即可,这便是改良后的分治算法。
已知[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]就这三种情况,也就是说如果[1,2]的值>[2],那么[2]就不是最大子数组,则去比较maxsum和[1,2],如果[1,2]的值<[2],那么我们重置目前的sum值(sum记录寻找过程中的最大子数组,即[j]和[1,j+1]中较大的值),让[2]的值和maxsum去比较。
同理,当求[1,3]时,我们已经知道了[1,2]的最大子数组,那么情况就分为三种了[1,2]的最大子数组,[3]或者[1,2,3],那么就比较[1,2,3]和[3],让大的一方去和maxsum去比较。
好,理解了原理,我们就可以写代码了。
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;
}
};
这个是关于题的。