剑指offer面试题42连续子数组的最大和

问题&＃xff1a;输入一个整数数组&＃xff0c;既有正数&＃xff0c;又有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

输入&＃xff1a;数组vector array

输出&＃xff1a;和最大值 int

思路&＃xff1a;贪心&＃xff0c;从前向后遍历数组&＃xff0c;当子数组和小于0时&＃xff0c;抛弃掉前面的子数组。同时&＃xff0c;设置maxSum保存子数组的和的最大值。

动态规划&＃xff0c;f(i)表示以i结尾的子数组的和的最大值&＃xff0c;递归公式如下&＃xff1a;

代码&＃xff1a;

class Solution {
public:bool isInvalidInput&＃61;false;int FindGreatestSumOfSubArray(vector array) {int len&＃61;array.size();if(len&＃61;&＃61;0){isInvalidInput&＃61;true;return 0;}int sum&＃61;0;int maxSum&＃61;INT_MIN;for(int i&＃61;0;imaxSum)maxSum&＃61;sum;}return maxSum;}
};

复杂度分析&＃xff1a;时间复杂度为O(n)&＃xff0c;空间复杂度为O(1).