上述题目太过复杂,于是我将他变了一种问法:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
简而言之,数组嘛,分为完整数组和子数组,这个题目中将的是:如果我这个数组中存在负数,找出这个数组中最大的子数组。例如输入的数组为{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},因此输出为该子数组的和18。
做法:
class Solution
{
public int FindGreatestSumOfSubArray(int[] array)
{
// write code here
//鲁棒判断
if (array.Length == 0)
return 0;
//定义连加运算常数a和最大值常数max(用于最后输出)
int max = array[0];
int a = 0;
//循环遍历
for(int i = 0;i<array.Length;i++)
{
//输入一个数组常数+a>这个输入的常数,加上他
if (array[i]+a>array[i])
{
a +=array[i];
}
//否则,把a等于他
else
{
a = array[i];
}
//最终输出判断
if(a>max)
{
max = a;
}
}
return max;
}
}