這題需要判斷最後加總是最大數字。
LeetCode 題目連結
https://leetcode.com/problems/maximum-subarray/
題目
Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Accept 作法
Runtime: 0 ms
Memory: 39.2 MB
Java 程式碼
- class Solution {
- public int maxSubArray(int[] nums) {
- int num = 0;
- int result = Integer.MIN_VALUE;
- for(int i = 0;i<nums.length;i++){
- num = Math.max(nums[i] + num,nums[i]);
- result = Math.max(result,num);
- }
- return result;
- }
- }
但是這題有提到要用 divide and conquer，故有另一種解法。時間複雜度為O(nlogn)
- class Solution {
- public int maxSubArray(int[] nums) {
- return getMaxValue(nums,0,nums.length - 1);
- }
- public int getMaxValue(int[] nums, int left,int right){
- if(left >= right) return nums[left];
- int mid = left +(right - left)/2;
- int leftMax = getMaxValue(nums,left,mid-1);
- int rightMax = getMaxValue(nums,mid+1,right);
- int mmax = nums[mid], t = mmax;
- for(int i=mid -1; i >= left;--i){
- t+=nums[i];
- mmax = Math.max(mmax,t);
- }
- t = mmax;
- for(int i = mid+1; i<=right;++i){
- t+=nums[i];
- mmax = Math.max(mmax,t);
- }
- return Math.max(mmax,Math.max(leftMax,rightMax));
- }
- }
更多 LeetCode 相關資源
複習程式面試書籍
除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。
需要的話可以看看，寫得很仔細。
沒有留言:
張貼留言