53.Maximum Subarray

【题目】

Given an integer arraynums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

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.

【思路】

那時候想說要用兩個迴圈去解

但後來其實只要把握好下面第二種方法的精隨

即可達到更有效率的解法

【解法】

☆JAVA

這是我自己想出來的 當時我一直想說只能用兩個迴圈去解

但此作法效率低 所以後來我一直在想有沒有更好的解法

class Solution {
    public int maxSubArray(int[] nums) {
        int result = 0;

        if(null != nums && nums.length > 0) {
            for(int i = 0 ; i < nums.length ; i++) {    //主迴圈
                int temp = nums[i];                    //先取第一個
                if(i == 0 || temp > result) {    
                    result = temp;                     //基本上第一次一定要進去 取最少一個答案
                }
                for(int j = i+1 ; j < nums.length ; j++) {    //次迴圈
                    int temp2 = nums[j];
                    temp = temp + temp2;
                    if(temp > result) {
                        result = temp;
                    }
                }
            }

        }


        return result;}}

後來看別人的解法才發現有一個迴圈可以解決的 這個方法有效率多了 且很好理解

基本上就把握好 負號<<正數<<加總正數

   public static int maxSubArray2(int[] nums) {
        int max_so_far =nums[0];
        int max_ending_here =0;
        for( int i=0; i< nums.length; i++)
          {
            max_ending_here = max_ending_here + nums[i];
            if(max_so_far < max_ending_here)
            {
              max_so_far = max_ending_here;
            }
            if(max_ending_here<0)
            {
              max_ending_here = 0;
            }
          }
        return max_so_far;
    }