關(guān)于今天打開了一道簡單題后開始懷疑人生這件事。。。

53. 最大子數(shù)組和

 

給你一個(gè)整數(shù)數(shù)組 nums ，請你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

 

子數(shù)組 是數(shù)組中的一個(gè)連續(xù)部分。

 

 

 

示例 1：

 

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

 

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/maximum-subarray

 

糾結(jié)了很多版本的代碼后，發(fā)現(xiàn)無法考慮完全，我的思路為：后一個(gè)加到前面時(shí)變大就繼續(xù)，變小就舍去，寫出了如下代碼，顯然是不可能ac的，

class Solution {

    public int maxSubArray(int[] nums) {

        int max=nums[0];

        int[] ans=new int[nums.length];

        int flag=0;

        for(int i=1;i<nums.length;i++){

            if(max+nums[i]>=max){

                max=max+nums[i];

            }else{

                ans[flag]=max;

                flag++;

                max=nums[i];

            }

        }

        Arrays.sort(ans);

        for(int i=0;i<nums.length;i++){

            System.out.println(ans[i]);

        }

        return ans[ans.length-1];

    }

}

思考后發(fā)現(xiàn)這如果涉及到后一個(gè)或兩個(gè)減小了但后面的第三個(gè)變大了，把三個(gè)都加上的收益大于就此斷開，我完全無法解決。就此思路我想了個(gè)較為極端的，若是中間隔著十幾個(gè)-1而最后為100，我該怎么知道他后面還有個(gè)大數(shù)能彌補(bǔ)過程中的損失呢。想了很久，沒有想明白，去看題解了。

贊最多為一個(gè)簡單但我沒太看懂原理的代碼：

class Solution {

    public int maxSubArray(int[] nums) {

        int res = nums[0];

        int sum = 0;

        for (int num : nums) {

            if (sum > 0)

                sum += num;

            else

                sum = num;

            res = Math.max(res, sum);

        }

        return res;

    }

}

[-2,1,-3,4,-1,2,1,-5,4]時(shí)

i=0：sum=0 num=-2-> sum=-2   res=-2

I=1:  sum=-2 num=1->sum=1   res=1

I=2: sum=1 num=-3->sum=-2    res=1

I=3: sum=0 num=4->sum=4     res=4

I=4:sum=4 num=-1->sum=3     res=4

I=5:sum=3 num=2->sum=5     res=5

I=6:sum=5 num=1->sum=6     res=6

I=7:sum=6 num=-5->sum=1    res=6

I=8:sum=1 num=4->sum=5     res=6

 

理了一遍看懂思路了，當(dāng)和大于零時(shí)將后面的值加上，反之則將sum等于下一值，每一輪循環(huán)都比較全局變量res和sum的大小。即sum大于零時(shí)比較res與子串和，小于等于0時(shí)比較比較res與此值大小。但判斷條件，sum是否大于0，這我還是沒有看懂，為什么以此為分界線呢。。。

而當(dāng)我看見以動(dòng)態(tài)規(guī)劃作為思路的解時(shí)發(fā)現(xiàn)，原來這就是動(dòng)態(tài)規(guī)劃：

 

 

作者：LeetCode-Solution

鏈接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

來源：力扣（LeetCode）

 

 

代碼如下：

class Solution {

    public int maxSubArray(int[] nums) {

        int pre = 0, maxAns = nums[0];

        for (int x : nums) {

            pre = Math.max(pre + x, x);

            maxAns = Math.max(maxAns, pre);

        }

        return maxAns;

    }

}

 

 

58. 最后一個(gè)單詞的長度

 

給你一個(gè)字符串 s，由若干單詞組成，單詞前后用一些空格字符隔開。返回字符串中 最后一個(gè) 單詞的長度。

 

單詞 是指僅由字母組成、不包含任何空格字符的最大子字符串。

 

 

 

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/length-of-last-word

 

這題確實(shí)簡單題，去掉首尾空格后找到最后一個(gè)空格，用長度-1去減空格位置即可

字符串中，trim()函數(shù)可去掉首位空格，lastIndexOf()函數(shù)可找到某個(gè)字符出現(xiàn)的最后位置，不過值得一提的是，其中的i是大寫- -，在這兒卡了好一會(huì)。

 

代碼如下：

class Solution {

    public int lengthOfLastWord(String s) {

        int k=0;

        s=s.trim();

        System.out.println(s);

        k=s.lastIndexOf(' ');

        return s.length()-k-1;

    }

}

 

翻了下答案，大家好像都在用split，記混了我以為split是python獨(dú)有來著。。那split會(huì)更方便一些。

今天還做了一些軟件工程的課程作業(yè)，是設(shè)計(jì)頁面，不得不說我確實(shí)沒有什么審美，做的我好費(fèi)勁。