Share my java solution


  • 0
    M

    First, tried Brute Force, which takes O(n^2). of course, it failed due to time limit exceeding.

    Second, tried Dynamic Programing, which takes O(n) time O(1) space.

    There are 2 cases, ith element is taken to Max(curr) or Not(nocurr).

    finally, return max between curr and nocurr.

    public int maxSubArray(int[] nums) {
        
        if(nums==null || nums.length<1)
            return 0;
            
        int curr   = nums[0]; // ith is included
        Integer nocurr = null;       // ith is not included
        
        for(int i=1;i<nums.length;i++){
            //ith is not included in max
            nocurr = nocurr==null? curr:Math.max(curr,nocurr);    
            
            //ith is included in max
            curr = Math.max(curr+nums[i], nums[i]);
        }
        
        return nocurr==null?curr:Math.max(nocurr, curr);
        
        // O(n^2)  - time limit exceeded
        // int[][] sum = new int[nums.length][nums.length];
        // Integer maxsum = nums[0];
        
        // for(int i=0;i<nums.length;i++){
        //     sum[i][i] = nums[i];
        //     for(int j=i+1;j<nums.length;j++){
        //         sum[i][j] = sum[i][j-1]=nums[j];
        //         maxsum = Math.max(maxsum,sum[i][j]);
        //     }
        // }
        // return (int)maxsum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.