[HackerRank] Practice Interview Preparation Kit: Dynamic Programming

Link: https://www.hackerrank.com/interview/interview-preparation-kit/dynamic-programming/challenges

---

1. Max Array Sum: https://www.hackerrank.com/challenges/max-array-sum/problem

Solution: Naive dynamic programming. Time = O(n), Space = O(1).

• Define 
• f(i): max subarray sum from 1 to i which contains the last element.
• g(i): max subarray sum from 1 to i which does not contain the last element.
• Answer = max(f(n), g(n)).
• Recursive formula:
• f(i) = g(i - 1) + a[i]
• g(i) = max(f(i - 1), g(i - 1)).

#!/bin/python3

import math
import os
import sys

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    best_w_last, best_wo_last = 0, 0
    for a in arr:
        best_w_last, best_wo_last = best_wo_last + a, max(best_w_last, best_wo_last)
    return max(best_w_last, best_wo_last)
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = list(map(int, input().rstrip().split()))
    res = maxSubsetSum(arr)
    fptr.write(str(res) + '\n')
    fptr.close()

---

2. Candies: https://www.hackerrank.com/challenges/candies/problem

Solution: Two pass greedy algorithm. Time = O(n), Space = O(n).

#!/bin/python3

import math
import os
import sys

# Complete the candies function below.
def candies(n, r):
    c = [1 for i in range(n)]
    for i in range(1, n):
        if r[i] > r[i - 1]:
            c[i] += c[i - 1];
    for i in range(n - 2, -1, -1):
        if r[i] > r[i + 1]:
            c[i] = max(c[i + 1] + 1, c[i])
    return sum(c)    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = []
    for _ in range(n):
        arr_item = int(input())
        arr.append(arr_item)
    result = candies(n, arr)
    fptr.write(str(result) + '\n')
    fptr.close()

---

3. Abbreviation: https://www.hackerrank.com/challenges/abbr/problem

---

4. Decibinary Numbers: https://www.hackerrank.com/challenges/decibinary-numbers/problem