iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
0
Software Development

LeetCode小試身手系列 第 4

【Day 4】#53 - 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.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解析

此題要在一個數字陣列裡找出有最大和的子陣列,例如陣列為 [-2,1,-3,4,-1,2,1,-5,4],則該陣列中的 [4,-1,2,1] 即為所求,因為其擁有最大的和為 6。

個人想法是可逐一加上每個值來求最大子陣列,基於A > A + (-B)的原理,若是當下的值(nums[i])大於暫存總和(sum)加上當下的值,例如前 n個總和為負數,第 n+1個數為正數,則取第 n+1個數為暫存總和,也就是 sum = nums[i]。

但是sum有可能隨著迴圈而變小,例如最後一個數為負數的情形 [-1,2,-3],所以要另外宣告一個變數用來紀錄真正的最大總和,也就是max。

需要特別注意的是,由於陣列裡的值有可能都是負數,例如 [-1,-2,-3],所以預設 max為Java中int型態的最小值Integer.MIN_VALUE(-2^31)而非 0。

解法

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

心得

Interger.MAX_VALUE = 2^31-1 = 2147483647 = 0x7FFFFFFFF
Interger.MIN_VALUE = -2^31 = -2147483648 = 0x80000000

Java規定整數型態的變數其長度為 4 Bytes,也就是有 32個Bit,為了方便顯示該值,以常見的 16進位制表示就是 0xZZZZZZZZ(可能您看到這邊也想Zzz了),每個 Z代表一個 16進位值佔有 4個Bit,總共有 32個Bit,所以整數的最大及最小值分別為上述值。


希望透過記錄解題的過程,可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知,若有更好的解法也歡迎留言,謝謝。


上一篇
【Day 3】#10 - Regular Expression Matching
下一篇
【Day 5】#66 - Plus One
系列文
LeetCode小試身手14

尚未有邦友留言

立即登入留言