【算法】LeetCode算法題-Maximum Subarray

這是悅樂書的第154次更新，第156篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級別的第13題（順位題號是53）。給定一個整數數組nums，找出一個最大和，此和是由數組中索引連續的元素組成，至少包含一個元素。例如：

輸入：[-2, 1, -3, 4, -1, 2, 1, -5,4]
輸出：6
說明：[4，-1,2,1]具有最大的和為6

輸入：[1, 2, 3]
輸出：6
說明：[1, 2, 3]具有最大的和為6

本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。

02 第一種解法

因為本題最后輸出的是最大值，所以需要進行求和，并且要從第一位元素開始，依次和相鄰元素相加來判斷。

第一次循環，得到數組第一個元素，與0相加，此時最大值是元素本身。

第二次循環，得到數組第二個元素，與第一個元素相加，此時相加的和需要先判斷是否大于第二個元素本身，因為如果兩個數的和還沒有本身大，那么此時最大和就是第二個元素本身。其次，還要和上一個和判斷，如果大于第一次循環得到的和，那么新的最大和即為第一個元素和第二個元素之和或者第二個元素本身；反之最大和依舊是第一次循環后的最大和。

后面的循環與上面一致，最開始第一次的循環也是如此，為了方便對比，只是詳細說明了第二次循環的處理邏輯。

public int maxSubArray(int[] nums) {int sum = 0;int max = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {sum += nums[i];if (nums[i] > sum) {sum = nums[i];}if (sum > max) {max = sum;}}return max;
}

對于上面的代碼，我們還可以再簡化下。

public int maxSubArray2(int[] nums) {int result = Integer.MIN_VALUE;int sum = 0;for (int i = 0; i < nums.length; i++) {sum = Math.max(nums[i] + sum, nums[i]);result = Math.max(result, sum);}return result;
}

03 第二種解法

還有一種思路，就是分而治之，將大問題拆分成小問題，找到小問題的答案后，最后合在一起再得出最后的答案。下面的代碼是討論區里某位大神的，可以好好看下。

public int maxSubArray3(int[] a) {return helper(a, 0, a.length - 1);
}int helper(int[] a, int l, int r) {if(l > r) return Integer.MIN_VALUE;if(l == r) return a[l];int mid = l + (r - l)/2;return Math.max(crossMidMax(a, l, r), Math.max(helper(a, l, mid - 1), helper(a, mid + 1, r)));
}int crossMidMax(int[] a, int l, int r) {int mid = l + (r - l)/2;int lmax = a[mid], lg =  a[mid];for(int i = mid -1; i >= l; i--) {lmax += a[i];lg = Math.max(lmax, lg);}int rmax = a[mid], rg =  a[mid];for(int i = mid +1; i <= r; i++) {rmax += a[i];rg = Math.max(rmax, rg);}return lg + rg - a[mid];
}

04 小結

今天此題涉及的分而治之算法，會寫在后面的算法和數據結構的理論知識介紹中，研究透徹了再和各位分享。以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支持！