# 20191224

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

sub - array
[-2, 1] -> -1
[-2, 1, -3] -> -4
[1, -3] -> -2

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]

// result 4
// ans 2
int ans = Integer.MIN_VALUE;
    
public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        for(int i = 0; i < nums.length; i++) { 
            ans = helper(i, nums, ans);
            System.out.println(ans);
        }
        
        return ans;
    }

     public int helper(int start, int[] nums, int ans) {
        int result = 0;
        for (int i = start; i < nums.length; i++) {
            result += nums[i];
            System.out.println("result " + result);
            ans = Math.max(result, ans);
            System.out.println("ans " + ans);
        }
        return ans;
    }    

// [-2,1,-3,4,-1,2,1,-5,4]
// [-2,1,-2,4,3,5,6,1,5]
// max = 6

public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        
        return max;
}

256. Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10

 Ｒ Ｂ Ｇ
[17,2,17] -> 2
[16,16,5] -> 5
[14,3,19] -> 3 (+
            -----
            10

Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.

[17,2,17]
[16,16,5]
[14,3,19]

16 += Math.min(2, 17)
16 += Math.min(17,17)
5 += Math.min(2, 17)

[17,2,17]
[18,33,7]
[14,3,19]

14 += Math.min(33, 7)
3 += Math.min(18, 7)
19 += Math.min(33, 18)

[17,2,17]
[18,33,7]
[21,10,38]

result = 10

public int minCost(int[][] costs) {
    if(costs==null||costs.length==0) {
        return 0;
    }
    
    for(int i=1; i<costs.length; i++){
        costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
        costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
        costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
    }
    
    int n = costs.length-1;
    return Math.min(Math.min(costs[n][0], costs[n][1]), costs[n][2]);
}