【微软面试一百题: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; }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容