题目
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n).
输入数组{1，-2,3,10，-4,7,2，-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和18。
解题思路
- 举例分析数组的规律
- 若从第一个数字开始的子数组的和小于从第三个数字开始的子数组的和，则不用考虑从第一个数字开始的子数组，之前的累加的和也抛弃
- 若从第三个数字开始累加和大于单独一个数字，则保留结果。观察后一位加上之后结果是否变小，若变小则不需要加后一位，若变大则加上后一位。
int GreateSubofArray(int *a,int length)
{
if( (a == NULL) || (length < 0) )
{
return 0;
}
bool flag_sub = false;
int sum_sub = 0;
int greateSum = 0;
for(int i = 0;i<length;i++)
{
if(sum_sub < 0)
{//从第一个数字开始的子数组的和小于从第三个数字开始的子数组的和
sum_sub = a[i];
}
else
{
sum_sub+=a[i];
}
if(sum_sub > greateSum)
{
greateSum = sum_sub;
}
}
return greateSum;
}
- 动态规划法
f(i)表示以第i个数字结尾的子数组的最大和。
image.png
这个公式的意义:
- 当以第i-1个数字结尾的子数组中所有数字之和小于0，则以第i个数字结尾的子数组就是第i个数字本身
- 若以第i-1个数字结尾的子数组中所有数字的和大于0，则与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和
int GreatestSubArray_2(int *a,int length)
{
int max = 0;
int temp= 0;
if( (a == NULL) || (length<0))
{
return 0;
}
for(int i = 0;i<length;i++)
{
temp = temp+a[i] > a[i] ? temp+a[i]:a[i];
max = max > temp ? max:temp;
}
return max;
}
