題目

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，所以整數的最大及最小值分別為上述值。

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