leetcode 150道题 计划花两个月时候刷完，今天（第五十三天）完成了3道(93-95)150：
93.（53. 最大子数组和）题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
第一版（这题我是一次写出来的，只不过我用了dp数组，没想到只用一个变量记录就行其他的都一样，那就看看我的代码吧，dp[i] 意思是数组到 i 结束 ）
class Solution {
public int maxSubArray(int[] nums) {
int len=nums.length;
if(len<=1){
return nums[0];
}
int[] dp=new int[len];
int max=nums[0];
dp[0]=nums[0];
for(int i=1;i<len;i++){
if(dp[i-1]<0){
dp[i]=nums[i];
}else{
dp[i]=nums[i]+dp[i-1];
}
max=Math.max(max,dp[i]);
}
return max;
}
}
94.（918. 环形子数组的最大和）题目描述：
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
第一版（这个题我感觉有点难度，没想出来，看了解题）
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int len=nums.length;
if(len<=1){
return nums[0];
}
int max=nums[0];
int min=nums[0];
int sum=nums[0];
int preMax=nums[0];
int preMin=nums[0];
for(int i=1;i<len;i++){
preMax=Math.max(nums[i]+preMax,nums[i]);
preMin=Math.min(nums[i]+preMin,nums[i]);
sum+=nums[i];
max=Math.max(max,preMax);
min=Math.min(min,preMin);
}
// 算一下有环的最大值
return max>0?Math.max(max,sum-min):max;
}
}
95.（35. 搜索插入位置）题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
第一版（这个题说实话应该很难，虽然我能偶尔写出来，但是我不知道啥时候应该给right=len 还是 right=len-1 还有while 结束条件 啥时候该有等号，啥时候不该有。。。不知道哪里有总结可以学习一下）
class Solution {
public int searchInsert(int[] nums, int target) {
int len=nums.length;
int left=0; int right=len-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
return left;
}
}
连着一周没开电脑了。。首先是冷这几天降温了房子里和冰箱一样。。还有就是变懒了。。变懒是最主要的。。
加油，早日跳槽！！！
