剑指offer--3题

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

第一感觉：看到这道题后，我先想的便是列出所有子数组，求取和再在这些和中求取最大值，这肯定是最简单的了！自己所写的代码如下：

#include "stdafx.h"
#include <iostream>int SubArraySumMax(int arr[], int len);using namespace std;int main(int argc, char* argv[])
{int arr[] = {1, -2, 3, 10, -4, 7, 2, -5};int summax = SubArraySumMax(arr,8);cout<<summax<<endl;return 0;
}int SubArraySumMax(int arr[], int len)
{int i,j;int summax = 0;int sum_temp;for(i=0; i<len; i++){if(summax < arr[i])summax = arr[i];sum_temp = arr[i];for(j=i+1; j<len; j++){sum_temp += arr[j];if(sum_temp > summax)summax = sum_temp;}}return summax;
}

但是这样的思路，其时间复杂度为O(n^2)，完全不符合题目所要求的O(n)。自己绞尽脑汁也未能想出更好的办法。。。

在看过标准答案后，惊叹于思想+代码的简单，不过很遗憾，自己并未豁然开朗。

关键未明白为什么可以这样做？根据评论，作者可能使用了所谓“动态规划”（DP）的方法，这应该是数据结构中的知识，看来自己还是井底之蛙，还要继续努力！

标准答案：

// jianzhioffer3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
//int SubArraySumMax(int arr[], int len);
bool FindGreatestSumOfSubArray
(int *pData,           // an arrayunsigned int nLength, // the length of arrayint &nGreatestSum     // the greatest sum of all sub-arrays
);
using namespace std;/*int main(int argc, char* argv[])
{int arr[] = {1, -2, 3, 10, -4, 7, 2, -5};int summax = SubArraySumMax(arr,8);cout<<summax<<endl;return 0;
}int SubArraySumMax(int arr[], int len)
{int i,j;int summax = 0;int sum_temp;for(i=0; i<len; i++){if(summax < arr[i])summax = arr[i];sum_temp = arr[i];for(j=i+1; j<len; j++){sum_temp += arr[j];if(sum_temp > summax)summax = sum_temp;}}return summax;
}*/int main()
{int arr[] = {1, -2, 3, 10, -4, 7, 2, -5};int nLength = 8;int nGreatestSum;bool IfSuccess = FindGreatestSumOfSubArray(arr,nLength,nGreatestSum);if(IfSuccess)cout<<nGreatestSum<<endl;elsecout<<"Input Error!"<<endl;return 0;
}/////
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////
bool FindGreatestSumOfSubArray
(int *pData,           // an arrayunsigned int nLength, // the length of arrayint &nGreatestSum     // the greatest sum of all sub-arrays
)
{// if the input is invalid, return falseif((pData == NULL) || (nLength == 0))return false;int nCurSum = nGreatestSum = 0;for(unsigned int i = 0; i < nLength; ++i){nCurSum += pData[i];// if the current sum is negative, discard itif(nCurSum < 0)nCurSum = 0;// if a greater sum is found, update the greatest sumif(nCurSum > nGreatestSum)nGreatestSum = nCurSum;}// if all data are negative, find the greatest element in the arrayif(nGreatestSum == 0){nGreatestSum = pData[0];for(unsigned int i = 1; i < nLength; ++i){if(pData[i] > nGreatestSum)nGreatestSum = pData[i];}}return true;
} 

PS：理解DP后，再来解决它！