題目描述

Maximum subarray sum

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

Max.sequence(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});

// should be 6: {4, -1, 2, 1}

>Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

>Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

***
###參考代碼
>```java
>public class Max {
    public static int sequence(int[] arr) {
        int max_ending_here = 0, max_so_far = 0;
        for (int v : arr) {
            max_ending_here = Math.max(0, max_ending_here + v);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
}

https://www.codewars.com/kata/maximum-subarray-sum/solutions/java
Author: mortonfox

解題思路

要點(diǎn)是若一段子數(shù)組arr[i]-arr[j]之和為負(fù)數(shù)，則以這段數(shù)組的下一個(gè)元素arr[j + 1]為終點(diǎn)的最大子數(shù)組之和必然為arr[j + 1]本身

用一個(gè)for語(yǔ)句遍歷數(shù)組arr，指針為i，每次循環(huán)更新兩個(gè)變量max_ending_here和max_so_far

變量max_ending_here是以arr[i]為結(jié)尾的最大子數(shù)組之和。拿題目中的例子來(lái)說(shuō)，假設(shè)指針i為1，則以arr[1]為結(jié)尾的最大子數(shù)組之和是1（即arr[1]自己）。當(dāng)指針i為5的時(shí)候，最大子數(shù)組之和則為5（即arr[3]+arr[4]+arr[5]）

變量max_so_far用來(lái)儲(chǔ)存問(wèn)題的答案，即到目前為止最大的子數(shù)組之和

每次循環(huán)，先將max_ending_here加上arr[i]，然后判斷是否小于0，若小于零則將其歸零。然后再比較max_ending_here和max_so_far，把最大值賦值給max_so_far

雜談

看到這個(gè)題目第一反應(yīng)就是動(dòng)規(guī)，因?yàn)殚L(zhǎng)的跟有向圖求最短路徑好像啊。去看了些關(guān)于貪心和DP的算法，但還是找不到思路。主要沒(méi)想通問(wèn)題的狀態(tài)是怎樣的。后來(lái)拖太長(zhǎng)時(shí)間了干脆暴力膜試了一次，居然過(guò)了（吐槽一下出題人也太懶了吧總共就三個(gè)test）。這個(gè)參考代碼是pass了以后看到的其他人的代碼，思路看一遍就能懂但是做題的時(shí)候就是想不出來(lái)就很氣o_o
還是得多刷題呀（扶額）

References

https://www.codewars.com/kata/maximum-subarray-sum/solutions/java