JZ42 连续子数组的最大和 #数组# #数学# #未分类#
解题思路:
思路一:#未分类#
- 基于数组本身特性
- 当前元素大于连续子数组和加上元素本身并且最大值比元素还小时,抛弃前面的连续子数组,重新开始计算连续数组和
- 加上当前元素后,数组和比最大值还大,则连续该元素
思路二:动态规划
扩展,使用动态规划算法进行解析
题解:
思路一:
class Solution
{
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
int cursum = array[0];
int maxsum = array[0];
for (int i = 1; i < array.size(); i++)
{
cursum += array[i];
if (cursum < array[i])
cursum = array[i]; //重新开始
if (cursum > maxsum)
maxsum = cursum; //连续
}
return maxsum;
}
};
思路二:#未完成#