微软等数据结构与算法面试100题 第三题
第三题
题目：
输入一个整型数组，数组里面有正数也有负数，数组中连续的一个或者多个数组成一个子数组，每个子数组都有一个和。
求，所有子数组的和的最大值。要求时间复杂度为O（n）
分析：
本题是一个典型的使用动态规划算法的题目。
动态规划算法的使用基本要素是1、最优子结构（当问题的最优解包含了其子问题的最优解，成该问题具有最优子结构性质）
2、重叠子问题（也就是说如果使用递归算法自顶朝下求解问题时，每次产生的子问题并不是新问题，有一些子问题被反复计算多次）。
对于本题，要求计算和最大的一个子数组，对于是不是最优子结构的分析，假设数组为a[] （size=n），那么可以分割成为0-n-2和1-n-1两个子问题。
这两个子问题里面又都包含1-n-2子问题，可以使用递归算法，但是由于使用递归算法会造成大量的子问题的求解，因此使用动态规划算法。
动态规划算法
设SUM[i]为前i个元素中，包含第i个元素且和最大的连续数组，result为已找到的子数组中最大的，对于第i+1个元素，有两种选择，1.作为新子数组的
第一个元素，2.放入前面找到的数组。
sum[i+1] = max(a[i+1],sum[i]+a[i+1]);
本题若使用顺序求解算法 复杂度为O(n^2)，递归求解算法复杂度为O(nlogn)，动态规划算法复杂度为O（n）
顺序求解
递归求解
动态规划
代码：
[cpp]
#include<iostream>
using namespace std;
int maxSubArray(int *a, const int length)
{
int maxSumSubArray = 0;
int sum_i = 0;
for(int i=0; i <length; i++)
{
sum_i = sum_i + a[i];
if(sum_i < 0) sum_i = 0;
else
{
if(sum_i > maxSumSubArray) maxSumSubArray = sum_i;
}
}
//若是数组中的元素均为负值
if(sum_i==0)
{
for(int i=0; i < length; i++)
{
if(a[i] > maxSumSubArray) maxSumSubArray = a[i];
}
}
return maxSumSubArray;
}
int main()
{
int a[10] = {1, 3, -3, -4 ,5 ,-2, 6, -1, 2, -6};
int length = sizeof(a)/sizeof(int);
cout<<maxSubArray(a,length);
return 0;
}
补充：软件开发 , C++ ,
