From subarray problems to Kadane and applications

Let’s start with a problem (src: leetcode#53) Given an integer array nums, find the subarray with the largest sum, and return its sum. Constraints: ・ 1 <= nums.length <= 1e5 ・ -1e4 <= nums[i] <= 1e4 Since subarray means to a contiguous non-empty sequence of elements within an array. It’s easy to find the trivial solution where we try to calculate all possible subarray. class Solution { public: int maxSubArray(vector<int>& nums) { int ans = INT_MIN; for (int l = 0; l < nums. Read more...

An Approach for DP Problem

Start with the problem (src: leetcode#714) You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Read more...

Complexity Classes

The following list contains common time complexities of algorithms: O(1) The running time of a constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer. O($\log n$) A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because $\log n$ equals the number of times n must be divided by 2 to get 1. Read more...

Dining Philosophers

algorithm lock concurrent
Bữa tối của các triết gia (dining philosophers problem) là một ví dụ nổi tiếng khi nhắc đến các vấn đề trong bài toán xử lý concurrent. Vấn đề được phát biểu như sau: Cho 5 triết gia ngồi chung một bàn tròn với 5 chiếc đũa xếp xem kẽ giữa 2 người ngồi cạnh nhau như hình img: Mỗi triết gia tìm cách để ăn được thức ăn từ đĩa của mình với điều kiện: “chỉ ai có 2 chiếc đũa cạnh mình mới được phép ăn”, do đó họ lần lượt đổi trạng thái giữa ăn (eating) và đợi (thinking) :)) Mỗi người sau khi giữa đôi đũa để ăn sau 1 khoảng thời gian phải bỏ lại 2 chiếc đũa về vị trí cũ để tiếp tục quá trình này. Read more...

Boundaries for algorithm analysis

algorithm approx
Some boundaries you should know to approximate time and space complexity of your algorithm. $2^{10} = 1,024 \approx 10^{3}, 2^{20} = 1,048,576 \approx 10^{6}$ 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of $2^{31} − 1 \approx 2 \times 10^{9}$ (safe for up to $\approx 9$ decimal digits) and $2^{63} − 1 \approx 9 \times 10^{18}$ (safe for up to $\approx 18$ decimal digits) respectively. Read more...

1 of 1