讨论/题目交流/🏆 第 153 场力扣周赛/
🏆 第 153 场力扣周赛

这是 9 月的第二场周赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验。

image.png

展开讨论

第三题O(n)解法,不用辅助数组,直接用两个辅助的数,分两种情况,一种是连续的子序列不删除,这个简单,O(n)搞定,另一种情况是连续子序列中删除一个,这种情况下,对于以J结尾的某个子序列来说,当新增第J+1个元素时只有两种情况,要么j+1直接添加到现有结果,要么j+1就是要删除的,对于j+1要删除的情况,只需要在找到前面最大的连续子序列即可。

class Solution {
public:
	int maximumSum(vector<int>& arr) {
		int arrLength = arr.size();

		if (1 == arrLength) {
			return arr[0];
		}
		int result = arr[0];

		int sum, presum, preSumMin, prepreSumMin, preMinMinux, prepreMinMinux;
		presum = arr[0];
		prepreSumMin = 0;
		prepreMinMinux = arr[0];
		int maxContinue = arr[0];
		for (int i = 1; i < arrLength; ++i) {
			sum = presum + arr[i];
			preSumMin = min(prepreSumMin, presum);
			maxContinue = max(maxContinue, sum - preSumMin);

			preMinMinux = min(arr[i] + prepreSumMin, prepreMinMinux);

			if (1 == i) {
				result = max(result, max(sum, maxContinue));
			}
			else {
				result = max(result, max(sum - preMinMinux, maxContinue));
			}

			presum = sum;
			prepreSumMin = preSumMin;
			prepreMinMinux = preMinMinux;
		}

		return result;
	}
};
展开全部 17 讨论