剑指offer第三十一题:连续子数组的最大和
1 //============================================================================ 2 // Name : JZ-C-31.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 连续子数组的最大和 7 //============================================================================ 8 9 #include10 #include 11 using namespace std;12 13 bool g_InvalidInput = false;14 15 int FindGreatestSumOfSubArray(int *pData, int nLength) {16 if ((pData == NULL) || (nLength <= 0)) {17 g_InvalidInput = true;18 return 0;19 }20 21 g_InvalidInput = false;22 23 int nCurSum = 0;24 int nGreatestSum = 0x80000000;//最小的整数。int 4个字节,最小数:-2^31:0x80000000,最大数:2^32-1:0x7fffffff。(均为补码)25 for (int i = 0; i < nLength; ++i) {26 if (nCurSum <= 0)27 nCurSum = pData[i];28 else29 nCurSum += pData[i];30 31 if (nCurSum > nGreatestSum)32 nGreatestSum = nCurSum;33 }34 35 return nGreatestSum;36 }37 38 // ====================测试代码====================39 void Test(char* testName, int* pData, int nLength, int expected,40 bool expectedFlag) {41 if (testName != NULL)42 printf("%s begins: \n", testName);43 44 int result = FindGreatestSumOfSubArray(pData, nLength);45 if (result == expected && expectedFlag == g_InvalidInput)46 printf("Passed.\n");47 else48 printf("Failed.\n");49 }50 51 // 1, -2, 3, 10, -4, 7, 2, -552 void Test1() {53 int data[] = { 1, -2, 3, 10, -4, 7, 2, -5 };54 Test("Test1", data, sizeof(data) / sizeof(int), 18, false);55 }56 57 // 所有数字都是负数58 // -2, -8, -1, -5, -959 void Test2() {60 int data[] = { -2, -8, -1, -5, -9 };61 Test("Test2", data, sizeof(data) / sizeof(int), -1, false);62 }63 64 // 所有数字都是正数65 // 2, 8, 1, 5, 966 void Test3() {67 int data[] = { 2, 8, 1, 5, 9 };68 Test("Test3", data, sizeof(data) / sizeof(int), 25, false);69 }70 71 // 无效输入72 void Test4() {73 Test("Test4", NULL, 0, 0, true);74 }75 76 int main(int argc, char** argv) {77 Test1();78 Test2();79 Test3();80 Test4();81 82 return 0;83 }