leetcode每日刷题计划-简单篇day6

突发奇想&胡思乱想的一天

银行家算法证明错了并挂在黑板上的可怜希希

Num 53 最大子序和 Maximum Subarray

O(n)的算法实现了，分治法有空补

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int a[100000];
        int ans=-1000;
        int len=nums.capacity();
        memset(a,0,sizeof(a));
        a[len-1]=nums[len-1];
        ans=nums[len-1];
        for(int i=len-2;i>=0;i--)
        {
            a[i]=max(nums[i],nums[i]+a[i+1]);
            if(a[i]>ans)
                ans=a[i];
        }   
        return ans;
    }
};

跳过了一个饶舌题，回头看

Num 58 最后一个单词的长度 Length of Last Word

注意有可能最后一个单词后面出现大段空格，更好的解决办法是倒序判断第一个非空格哦。

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len=s.length();
        int ans=0;
        for(int i=0;i<=len-1;i++)
        {
            if(s[i]==' ' && i!=len-1 && s[i+1]!=' ') ans=0;
            else if(s[i]!=' ')ans++;
        }
        return ans;
    }
};