C++LeetCode 53:最大サブシーケンス和

前言このテーマには3つの解法があります.

暴力解法:すべてのサブシーケンスと、最大のものを見つける.時間複雑度O(n^2)

分治法:求めたシーケンスを2つに分けて、それぞれ左、右のサブシーケンスの最大和を求めて、それから中間の境界の最大和を求めて、最後に3つの大きさを比較して、最大の1つを見つけます.時間複雑度O(nlog(n))

オンライン処理:シーケンスを順次巡回して和を求め、負のすべての値を捨て、すなわちゼロにし、最後に和の最大値を求める.時間複雑度O(n)

トピックは、整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列に少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.例:入力:[-2,1,-3,4,-1,2,1,-5,4],出力:6解釈:連続サブ配列[4,-1,2,1]の和が最大で6である.
実現方法一、暴力の解

int MaxSubseqSum1(int a[], int n) {
	int CurrentSum, MaxSum = 0;
	for (int i = 0; i < n; i++) {
		CurrentSum = 0;
		for (int j = i; j < n; j++) {
			CurrentSum += a[j];
			if (CurrentSum > MaxSum)
				MaxSum = CurrentSum;
		}
	}
	return MaxSum;
}

二、分治法

//3     ，     
int MaxNum3(int a, int b, int c) {
	return a > b ? a > c ? a : c : b > c ? b : c;
}

//   :  。 O(nlog(n))
int BinaryMaxSubSum(int list[], int left, int right) {
	int MaxLeftSum, MaxRightSum;
	int MaxBoardSum, MaxLeftBoardSum = 0, MaxRightBoardSum = 0;
	int i, center;

	//        
	if (left == right) {
		if (list[left] > 0)
			return list[left];
		return 0;
	}

	//    ，         、       
	center = (left + right) / 2;
	MaxLeftSum = BinaryMaxSubSum(list, left, center);
	MaxRightSum = BinaryMaxSubSum(list, center + 1, right);
	
	//          
	int LeftBoardSum = 0, RightBoardSum = 0;
	for (i = center; i >= left; i--) {
		LeftBoardSum += list[i];
		if (LeftBoardSum > MaxLeftBoardSum) {
			MaxLeftBoardSum = LeftBoardSum;
		}
	}
	for (i = center + 1; i <= right; i++) {
		RightBoardSum += list[i];
		if (RightBoardSum > MaxRightBoardSum) {
			MaxRightBoardSum = RightBoardSum;
		}
	}
	MaxBoardSum = MaxLeftBoardSum + MaxRightBoardSum;

	//       ，     
	return MaxNum3(MaxBoardSum, MaxLeftSum, MaxRightSum);
}

int MaxSubseqSum2(int a[], int n) {
	return BinaryMaxSubSum(list, 0, n - 1);
}

三、オンライン処理

int MaxSubseqSum3(int a[], int n) {
	int CurrentSum = 0, MaxSum = a[0];
	for (int i = 0; i < n; i++) {
		CurrentSum += a[i];
		if (CurrentSum > MaxSum) {
			MaxSum = CurrentSum;
		}
		if (CurrentSum < 0) {
			CurrentSum = 0;		//        ，   
		}
	}
	return MaxSum;
}

上の3つの方法を比較して、3つ目の方法が一番いいです.しかし、分治法の思想もすばらしく、身につけなければならない.