LeetCode 53. Maximum Subarray and 121. Best Time to Buy and Sell Stock最大子数组问题

LeetCode 53. Maximum Subarray

Description:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Difficulty:Easy

Solution #1（提交版本）：时间复杂度O(n)

此题的一个特例：当所有数都为负数时，需要返回一个最小的负数，而不是返回0。
设临时子数组和为sum[len]（len为数组长度），sum[0]初始化为nums[0]，i从1一直遍历到len-1

当当前sum[i-1]的值为正数时，加上nums[i]，赋值给sum[i]，此时如果nums[i]为负数，接下来max_sum经过max函数处理后变得更小，为什么要加入一个负数呢？因为我们求的是连续的子数组，加入后以备后用；如果nums[i]为正数，接下来max_sum经过max函数处理后变得更大。
当当前sum[i-1]的值为负数时，舍弃掉sum[i-1]，直接把nums[i]赋值给sum[i]，因为前面子数组之和已经是负数的话，再加上nums[i]也肯定不是所求的解，直接从nums[i]开始重新计算sum[i]，max_sum也随之改变。

代码实现：

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int len = nums.size();
		vector<int> sum(len);
		sum[0] = nums[0];
		int max_sum = sum[0];
		for (int i = 1; i < len; i++) {
			sum[i] = nums[i] + (sum[i - 1] > 0 ? sum[i - 1] : 0);
			max_sum = max(max_sum, sum[i]);
		}
		return max_sum;
	}
};

Solution #2（分治法）：时间复杂度O(nlogn)

分治法的精髓：

分-将问题分解为规模更小的子问题
治-将这些规模更小的子问题逐个击破
合-将已解决的子问题合并，最终得出原问题的解

所以原数组的最大子数组可以采用如下分治法求解：

分-将原数组拆分成两部分，每个部分再拆分成新的两部分…直到数组被分解成只剩下一个元素
治-每个分解后的数组找最大的子数组，只有一个元素的数组，解就是该元素
合-将每个分解后的数组求解得到的最大子数组合并为一个数组，其中解有三种可能：
左边的返回值最大；
右边的返回值最大；
中间存在一个更大的子数组之和。
我们需要比较返回值，然后得到最大的返回值，即可得到解。

根据《算法导论》上详细的介绍以及伪代码，可编写出如下代码：

// 存储结果：最大子数组的下标以及和
struct PositionASum {
	int low;
	int high;
	int sum;
};
// 寻找包含中点位置的最大子数组函数
PositionASum MaxCrossingSubarray(int a[], int low, int mid, int high) {
	// 求中点左边的最大值和最大位置
	int maxLeft;// 记录左边的最大位置
	int maxSumLeft = -1000000;// 记录左边的最大和
	int sumLeft = 0;
	for (int i = mid; i >= low; i--) {
		sumLeft += a[i];
		if (sumLeft > maxSumLeft) {
			maxSumLeft = sumLeft;
			maxLeft = i;
		}
	}
	// 求中点右边的最大值和最大位置
	int maxRight = mid + 1;// 记录右边的最大位置
	int maxSumRight = -1000000;// 记录右边的最大和
	int sumRight = 0;
	for (int i = mid + 1; i <= high; i++) {
		sumRight += a[i];
		if (sumRight > maxSumRight) {
			maxSumRight = sumRight;
			maxRight = i;
		}
	}
	PositionASum p;
	p.low = maxLeft;
	p.high = maxRight;
	p.sum = maxSumLeft + maxSumRight;
	return p;
}
// 分治法左右
PositionASum FindMaxSubArray(int a[], int low, int high) {
	if (low == high) {
		PositionASum p;
		p.low = low;
		p.high = high;
		p.sum = a[low];
		return p;
	}
	else {
		int mid = (low + high) / 2;
		PositionASum left = FindMaxSubArray(a, low, mid);
		PositionASum right = FindMaxSubArray(a, mid + 1, high);
		PositionASum cross = MaxCrossingSubarray(a, low, mid, high);
		if (left.sum >= cross.sum && left.sum >= right.sum) {
			return left;
		}
		else if (right.sum >= left.sum && right.sum >= cross.sum) {
			return right;
		}
		else {
			return cross;
		}
	}
}
int main() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	PositionASum res = FindMaxSubArray(a, 0, n);
	cout << "low: " << res.low << endl << "right: " << res.high << endl << "MaximumSubarray: " << res.sum << endl;
	return 0;
}

Solution #3（暴力破解法）：时间复杂度O(n^3)

列出数组所有可能的组合，比较找出其中和最大的组合即可。
分三层循环：

第一层循环用于固定子数组的起始位置
第二层循环用于确定子数组的结束位置
第三层循环用于子数组和的计算，从子数组的底部开始遍历到尾部，累加起来就是该子数组的和

// 暴力求解法O(n^3)
int main() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	//int array_length = sizeof(A) / sizeof(A[0]);//数组大小
	int max_sum = -10000000;// 记录子数组的和，但是超过int的表示范围时有问题
	int low;// 记录子数组的底
	int height;// 记录子数组的高
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			int array_sum = 0;// 记录所遍历的子数组的和
			// 计算遍历的子数组的和
			for (int k = i; k <= j; k++) {
				array_sum += a[k];
			}
			// 找出最大子数组
			if (array_sum > max_sum) {
				max_sum = array_sum;
				low = i;
				height = j;
			}
		}
	}
	cout << "low: " << low << endl << "right: " << height << endl << "MaximumSubarray: " << max_sum << endl;
}

Solution #4：时间复杂度O(n^2)

一种比暴力破解法更高效的算法：相比于暴力破解法每一次都需要从i到j重新计算一次，这种算法每一次只需要在原来计算后的基础上加上一个数，所以这种算法少了一层循环，时间复杂度为O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int sum = 0;// 最大子数列之和
	// 寻找最大子数列
	for (int i = 0; i < n; i++) {
		int curSum = 0;// 当前数列之和
		for (int j = i; j < n; j++) {
			curSum += a[j];
			if (curSum > sum) {
				sum = curSum;
			}
		}
	}
	if (sum < 0) {
		cout << '0' << endl;
	}
	else {
		cout << sum << endl;
	}
	return 0;
}

Solution #5：时间复杂度O(n^2)

《算法导论》上习题4.1-5提出了这么一种算法：从数组的左边界开始，由左至右处理，记录到目前为止已经处理过的最大子数组。
若已知A[1..j]的最大子数组，基于如下性质将解扩展为A[1..j+1]的最大子数组：A[1..j+1]的最大子数组要么是A[1..j]的最大子数组，要么是某个子数组A[i..j+1] (1≤i≤j+1)。
代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int low = 0;// 记录子数组的底
	int high = 0;// 记录子数组的高
	int max_sum = a[0];// 记录最大子数组的和
	for (int i = 0; i < n - 1; i++) {
		int sum = 0;
		// 寻找以A[i+1]为终点的最大子数组
		for (int j = i + 1; j >= 0; j--) {
			sum += a[j];
			if (sum > max_sum) {
				max_sum = sum;
				low = j;
				high = i + 1;
			}
		}
	}
	cout << "low: " << low << endl << "right: " << high << endl << "MaximumSubarray: " << max_sum << endl;
	return 0;
}

Solution #1:

同样的问题，只不过输入是原始数组，我们得先把它转换成相邻差值的数组。比如Example 1输入是[7 1 5 3 6 4]，我们先把它转换成[7 -6 4 -2 3 -2]，然后就是类似求最大子数组问题了，但最重要的一点是我们必须排除数组的第一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int len = prices.size();
		if (!len) return 0;
		vector<int> sub(len);
		sub[0] = prices[0];
		// 求相邻之间的差值变化
		for (int i = 1; i < len; i++) {
			sub[i] = prices[i] - prices[i - 1];
		}
		int maxCur = 0, maxSoFar = 0;
		for (int i = 1; i < len; i++) {
			maxCur += sub[i];
			maxCur = max(0, maxCur);
			maxSoFar = max(maxCur, maxSoFar);
		}
		return maxSoFar;
	}
};

LeetCode 53. Maximum Subarray

Description:

Solution #1（提交版本）：时间复杂度O(n)

代码实现：

Solution #2（分治法）：时间复杂度O(nlogn)

Solution #3（暴力破解法）：时间复杂度O(n^3)

Solution #4：时间复杂度O(n^2)

Similar Questions

Solution #1: