数组01

题目:返回一个整数数组中最大子数组的和。

要求：

　　1、 输入一个整形数组，数组里有正数也有负数。

　　2、 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

　　3、 求所有子数组的和的最大值。要求时间复杂度为O(n)

设计思想：

　　核心算法：动态规划。

　　刚开始的时候并没有找到合适的算法，只能够设置数组的长度为特定的数值，然后每一种情况都考虑到，但是对于很大的数值来说，就无法实现了，直到找到了动态规划方法，然后才解决了核心的算法问题，时间复杂度为O（n）满足题目需求。

源代码：　

//数组1
//胡浩特、朱子嘉 2016/3/21

#include<iostream>
using namespace std;

int MaxSum3(int a[], int n){//优化方案 时间O（n） 空间  O(1)
    //int A，N;
    int nStart = a[n - 1];
    int nAll = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        if (nStart<0)
            nStart = 0;
            nStart += a[i];
        if (nStart>nAll)
            nAll = nStart;
    }
    return nAll;
}
int main()
{

    int i, length;
    cout << "请输入数组长度：";
    cin >> length;
    int a[50];
    cout << "请输入数组值：";

    for (i = 0; i < length; i++)
    {
        cin >> a[i];
    }
    

    cout<<MaxSum3(a, length)<<endl;
    return 0;
}

结果截图：

　　三组测试数据：

　　1、都为正数，最大值为数组之和。

　　

　　2、都为负数，结果为最大的负数。

　　

　　3、有正数有负数还有有0。

　　

实验总结：

　　整个实验的关键在于算法的实现，对于这个问题来说有三种合适的算法，但是只有动态规划才满足时间复杂度的要求。通过查找资料和自己研究才找到合适的算法。对于我来说，实验很简单但是还是花费了不少的努力。这一次实验是一个新的开始，希望自己可以做好数组的一系列的实验。