深圳网站设计哪好,投资网站php源码,wordpress 笔记插件,联合办公空间53. 最大子数组和
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。子数组是数组中的一个连续部分。
示例 1#xff1a; 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4]
输…
53. 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。
示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。 示例 2 输入nums [1]
输出1 示例 3 输入nums [5,4,-1,7,8]
输出23 提示 1 nums.length 105-104 nums[i] 104 题目分析
思考1从第一个数开始累加找到累加最大的数和最小的数然后用最大的减去最小的。其中最大的数要在最小的数右边。结果失败忽略了一个数字的时候以及整个数列都是负数时会运行错误。
代码如下
class Solution {
public:int maxSubArray(vectorint nums) {int len nums.size();int sum 0;int a[100002];a[0] 0;int max a[0];int min a[0];if (len 1) {return nums[0];}else{for (int i 0; i len; i) {sum nums[i];a[i 1] sum;}int maxi;for (int i 0; i len 1; i) {if (a[i] max) {max a[i];maxi i;}}for (int j 0; j maxi; j) {if (a[j] min) {min a[j];}}int res max - min;return res;}}
};
思考2通过动态规划的思想依旧是从前往后加但是如果前一个是负数就不要累加重新加当前的值。最后找最大的累加值即可。
代码如下
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();int maxnum nums[0];for (int i 1; i n; i) {if (nums[i - 1] 0) {nums[i] nums[i - 1];}maxnum max(maxnum, nums[i]);}return maxnum;}}; 118. 杨辉三角
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。在「杨辉三角」中每个数是它左上方和右上方的数的和。
示例 1: 输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: numRows 1
输出: [[1]] 提示: 1 numRows 30 代码如下
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint a(numRows);// a[0][0]1;// a[1][0]1;// a[1][1]1;for (int i 0; i numRows; i) {a[i].resize(i 1);for (int j 0; j i; j) {if (i 0 || i 1 || j 0 || j i) {a[i][j] 1;}else{a[i][j] a[i - 1][j] a[i - 1][j - 1];}}}return a;}
};
