题目:
输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 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; }
