【微软面试一百题：3】求子数组的最大和

题目:
输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4, 7, 2, 因此输出为该子数组的和 18。

提供两种做法：

• 动态规划

#include <iostream>
#include <string>
using namespace std;

#define size 10
//返回一个数组的最大值
int max(int data[])
{
    int temp=data[0];
    for(int i=1;i<size;i++)
    {
        if(temp<data[i])temp=data[i];
    }
    return temp;
}

//采用动态规划方法
int cal(int arr[])
{
    int data[size]{};//增加一个临时数组用来存放第i个值的时候的最大值
    data[0]=arr[0];
    for(int i=1;i<size;i++)
    {
        if(data[i-1]<0)data[i]=arr[i];
        else
        {
            data[i]=data[i-1]+arr[i];
        }
    }
    return max(data);
}

int main()
{
    
    int arr[]={31,-41,59,26,-53,58,97,-93,-23,84};
    cout<<cal(arr)<<endl;;
    return 0;
}

• 贪心

int maxSubarray(int a[], int size) {
if (size<=0) error(“error array size”);
int sum = 0;
int max = - (1 << 31); int cur = 0;
while (cur < size) {
sum += a[cur++];
if (sum > max) { max = sum;
} else if (sum < 0) { sum = 0;
} }
return max; }