マイクロソフトの面接試験の100題のシリーズ－第3題

注:マイクロソフトの面接試験の100題シリーズの中の題はすべてv〓です.JULYv(http://blog.csdn.net/v_JULY_v)収集した面接問題について、具体的なPDFダウンロード住所は以下の通りです.http://download.csdn.net/detail/v_jurlyuv/4583815
 文章を書く目的は自分を鍛えることです.大牛さんのアドバイスを歓迎します.
 問題3:サブ行列の最大和
行列の整数を入力します.行列には正の数もあれば、負の数もあります.
配列内の連続する1つまたは複数の整数は1つのサブアレイを構成し、各サブアレイは1つの和を有する.
すべてのサブアレイの和の最大値を求めて、時間の複雑さはO(n)です.
例えば、入力の配列は1、−2、3、10、−4、7、2、−5であり、最大のサブアレイは3、10、−4、7、2であるため、出力はこのサブアレイの和18である.
私の思考過程:

時間の複雑さはO(n)であり、配列を巡回するしかない.

は現在の最大値を記録し、数を経るごとに現在の和に加算されます.積算後、現在と現在の最大値を比較すると、現在の最大値より大きい値が入れ替わります.現在と負の数があれば、累積しても意味がないので、現在と負の数は0を捨てて新たな積算を始めるべきです.

コードは以下の通りです

//written by zero
#include <iostream>
using namespace std;

int MaxSum(int a[], int size)
{
	int sum = 0;
	int curMax = -(1 << 31);

	for (int i = 0; i < size; ++i)
	{
		sum += a[i];

		if (sum > curMax)
			curMax = sum;

		if (sum < 0)
			sum = 0;
	}
	return curMax;
}

int main()
{
	int a[8] = {1,-2,3,10,-4,7,2,-5}; 
	cout << "max sum of a: " << MaxSum(a,8) << endl;

	int b[4] = {-5,8,-1,6};
	cout << "max sum of b: " << MaxSum(b,4) << endl;
	return 0;
}

実行結果: