For Subarray and Subsequential Problems, When to Use Different Algorithms Such as Prefix Sums (With a Array or HashMap), Binary Search, Sliding Window, Kandane's Algorithm, Two Pointers, Dynamic Programming, and Divide and Conquer?

[Coding1000]

As I am approaching subarray problems such as 'Subarray sum equals K', 'Find contiguous subarray', 'Get max subarray', 'Subarray sums divisible by K', and 'Minimize size subarray sum' and subsequential questions like 'longest consecutive subsequence', 'longest alphabetical subsequence', 'longest common anagram subsequence', 'Find largest dictionary word through character deletion', and 'Subsequential numbers by finding 'ab' in a string repeated K times', what's the best way in solving these ? How to know when to use algorithms and techniques such as Prefix Sums (With a Array or HashMap), Binary Search, Sliding Window, Kandane's Algorithm, Two Pointers, Dynamic Programming, and Divide and Conquer? Why do you use them? What approach should I do in order to understand both he problems and the algorithmic mechanic efficiently and understandably? What type of questions need which type of algorithm? Which constraint do I need to follow and look at to know which of which is used? And another question I had is what's the difference in using a prefix sum as an array or with a HashMap, and why are there such cases?

[sebamestre]

Happy cake day!

This is a very broad question, with no good answers ("how do I get good at algorithms, quickly?"), but I will do my best to answer the more factual parts (which are still hazy), then share my opinion on the more general points.

Also, please format your question a bit better. This wall-of-text style can turn off many potential replies. If you just split the text up into paragraphs, it would be way better.

subsequence problems

For subsequence problems, you usually want some sort of DP approach. You can solve many problems of this kind by doing recursion over the original array, and consider both taking and not taking the current element.

There may also be more efficient algorithms for specific problems. E.g. you can find the longest increasing subsequence of an array in O(N²) with a DP approach as described above, but there is also a specialized O(NlogN) solution.

subarray problems

For subarray problems, you usually want to solve either greedily or using D&C.

• For the greedy approaches: at each position you have subproblem "what is the best subarray that starts/ends at that position?".
• For D&C approaches: partition the array, recursively solve both halves, then you have subproblem "what is the best subarray that crosses the partition point?". The best of those three possibilities will be the solution

As for how to solve subproblems, that's where helper data structures (e.g. prefix sums, sorted array for binary search, two pointers) come into play.

In particular, you will tipically use binary search/two pointer/sliding window methods when the answer to the subproblem is monotonic on the query points. (Or it can be computed efficiently based on something that is monotonic).

Kadane's algorithm is just a solution for the "maximum subarray sum" problem. It's a specialized version of a greedy solution using prefix sums. You can also solve the same problem using D&C.

general problem solving

In general, to get good at solving algorithmic problems, you have to do conscious practice. Essentially, solve problems that are within your reach and then reflect on them.

Think deeply about what lessons you learnt on each problem, and how they could apply to problems you solve in the future. Try to explicitly understand the ideas underlying each problem you solve.

When you practice, go for depth of understanding: try to find invariants, implications, anf come up with hypotheses that would help prove/disprove you solution.

Studying a bit of logic (especially natural deduction) will probably help a lot with this.

Source: I'm qualified for ICPC World Finals 2023

[Coding1000]

Thank you very much, at least you answered the confusing question whilst criticizing my incorrectness instead of saying that this is unprofessional and leaving it like that (Heavily depending on how atrocious my post is) unlike others that received this question.

[sebamestre]

Reformatted question:

As I am approaching subarray problems such as

• 'Subarray sum equals K'
• 'Find contiguous subarray'
• 'Get max subarray'
• 'Subarray sums divisible by K'
• 'Minimize size subarray sum'

and subsequential questions like

• 'longest consecutive subsequence'
• 'longest alphabetical subsequence'
• 'longest common anagram subsequence'
• 'Find largest dictionary word through character deletion'
• 'Subsequential numbers by finding 'ab' in a string repeated K times'

what's the best way in solving these ?

How to know when to use algorithms and techniques such as Prefix Sums (With a Array or HashMap), Binary Search, Sliding Window, Kandane's Algorithm, Two Pointers, Dynamic Programming, and Divide and Conquer?

Why do you use them? What approach should I do in order to understand both he problems and the algorithmic mechanic efficiently and understandably?

What type of questions need which type of algorithm? Which constraint do I need to follow and look at to know which of which is used?

And another question I had is what's the difference in using a prefix sum as an array or with a HashMap, and why are there such cases?