DEV Community: Ayan Banerjee

MediDoc: Efficient Paperless Medical Treatment Management System - DOHackathon Submission

Ayan Banerjee — Sun, 10 Jan 2021 19:36:30 +0000

What I built

MediDoc - an efficient medical treatment management system.

Category Submission:

Built for Business. The target customers of this app are governments and connected hospitals.

App Link

https://medi-doc-njgqo.ondigitalocean.app/

Description

This is an end to end application for medical treatment management.

A typical treatment case in hospital:

Take admission in a hospital
Hospital prescribes some medicines in a paper and the patient (or the family of the patient) has to buy it from a pharmacy
Hospital asks the patient to get some diagnosis (say, MRI, X-ray, etc.), and it is performed in a diagnosis center. The patient gets the scanning done and finally brings the result back to the hospital. S/he may have to wait quite some time in the diagnosis center to get paper-works done and get those scanning results.

So as we can see, there are quite a few manual steps in the flow of work, and in many places, paperwork is involved.

MediDoc is a web app that tries to get rid of this paperwork and thus making the whole process much more efficient.

In this web app, there are 4 types of users:

Normal user (or patient)
Hospital
Pharmacy
Diagnosis Center

Only admins can add hospital, pharmacy, and diagnosis type of users. Admins ideally should be the government-appointed personnel, who can approve hospitals, pharmacies, and diagnosis centers after checking their license. Admins can also add more admins.

Screenshots

Medical Sign Up

Dashboard (only available to admin)

Add User

Successfully Added User

Add Admin

Search Medical User

Homepage - Recent Cases, Search and Bookmarked Cases

All Cases

Search Cases

A Case

Edit Description

Add Comment

Edit Comment

Add User to Case

Upload File

Library

Error Page

Demo

Salient Features

Access Level: Once a user is added, they will see their kind of data only. For example, a pharmacy can see only prescription-related comments and files. In this way, they only get to see what is relevant to them. It is up to the hospital and patient to provide relevant information to different types of users.
My Library: If we think a file will be useful later, we can add it to our library by clicking on the + button on the file. It can be accessed by clicking on the profile icon in the top right and then clicking on the library. One can remove files from the library as well.
Maintain Case Activity: Once a case is resolved, it can be marked as inactive by clicking on the EDIT button in the description panel, and unchecking the Is active checkbox. The case will no longer show up on the recent cases list.
Search for Hospitals, Pharmacies, and Diagnostic Labs

Next Steps

Create public APIs, so that other apps can consume data of this web app
Add billing feature

Advantages

Zero paperwork, a patient fills the required information (blood group, allergies, etc.) during sign up
No paperwork for prescriptions as well
Documents (e.g., x-ray scan) can be saved in my library and referenced later
Past case histories can be referenced for similar cases in future
Patients no longer have to wait to fill in forms and then to obtain results from diagnostic labs. Labs can upload the documents (say, X-ray) once it is processed.

Link to Source Code

ayan-b/MediDoc

Permissive License

MIT

Background

My inspiration comes from a real-world experience when I visited a hospital a few years ago. There I observed at a significant amount of time is wasted in duplicated paperwork activities (for example, submitting the same documents in both hospital and diagnosis lab) which can be automated using technology.
I also came across this thread a couple of months ago which asserted my belief that this is not a local issue!

How I built it

I have used DigitalOcean app platform, database, and DigitalOcean spaces in this project.

Deploying Django with the DigitalOcean Apps Platform was fairly straightforward. The app platform easily identified that this is a Django through the presence of the wsgi.py file. Deploying Django is also thoroughly documented and thus I didn't encounter any hiccups.

After connecting my GitHub repo with the app platform, the only thing I had to change was the run command: gunicorn --worker-tmp-dir /dev/shm medidoc.wsgi. I have also used some environmental variables:

DJANGO_SECRET_KEY for well ... DJANGO_SECRET_KEY
I also have another environment variable IS_PROD (default to False) which is used to control the static file hosting.
Since in MediDoc users can upload media, I also had to create DigitalOcean spaces and add the following configuration variables to my settings.py file.

if IS_PROD:
    DEFAULT_FILE_STORAGE = 'storages.backends.s3boto3.S3Boto3Storage'
    AWS_S3_REGION_NAME = 'nyc3'
    AWS_S3_ENDPOINT_URL = f'https://{AWS_S3_REGION_NAME}.digitaloceanspaces.com'
    AWS_ACCESS_KEY_ID = os.getenv('AWS_ACCESS_KEY_ID')
    AWS_SECRET_ACCESS_KEY = os.getenv('AWS_SECRET_ACCESS_KEY')
    AWS_STORAGE_BUCKET_NAME = 'medidoc'
    AWS_S3_OBJECT_PARAMETERS = {
        'CacheControl': 'max-age=86400',
    }
    AWS_LOCATION = 'media'
    AWS_S3_ADDRESSING_STYLE = 'virtual'
    AWS_QUERYSTRING_EXPIRE = 7 * 24 * 60 * 60
    AWS_S3_BUCKET_AUTH = False

In the end, I have the following environment variables:

Through the hackathon, I learned a lot about Digital Ocean and deploying a production-ready app!

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit, or use the admin account below to approve!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

the patient account:

devto-patient

and the admin account:

devto

Password for all of them is: medidocpass@abc

I would love to hear your feedback. Let me know what you think!

Additional Resources/Info

Backend:

Django
Material Form for rendering forms

Frontend:

MaterializeCSS framework

Credits

Favicon by Icons for Free
Chest x-ray photo by CDC on Unsplash
Hand xray photo by Owen Beard on Unsplash

MediDoc: Update 6 - Search Medical Institutions

Ayan Banerjee — Mon, 04 Jan 2021 13:10:16 +0000

Medical Search

Today, I added the search medical institution page. This is the same as the search case page but, searches for medical institutions (hospitals, pharmacies, diagnosis centers). To implement this, the module django_simple_search is used.

from django_simple_search import search_filter

def search_medical(request):
    queries = request.GET.get('q')
    if queries is not None:
        search_fields = ['username', 'address', 'mobile_no', 'emergency_mobile', 'pin_code', 'other_info']
        split_queries = queries.split()
        users = None
        for query in split_queries:
            current_users = User.objects.filter(
                search_filter(search_fields, query),
                is_active=True,
                groups__name__in=['hospital', 'pharmacy', 'diagnosis_center'],
            )
            if users is None:
                users = current_users
            else:
                users = users.union(current_users)
        return render(request, 'cases/search-medical.html', {'users': users, 'search_term': queries})
    else:
        return render(request, 'cases/search-medical.html')

In short, the query string is passed via the URL (like https://example.com?q=kolkata). I grab this query string using request.GET.get('q'). After that, it is split into multiple queries (for example, 'Hello World' will be split into 'Hello' and World and thus be two different queries). Then, I query the User model using search_filter for all the queries and at the end, they are unionized and passed to the template.

This marks the end of all feature implementation I had in mind at the start of the hackathon. Let me know if you have any features that you would like to see in the web app! 😄

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit or you can also use the admin account mentioned below!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

the patient account:

devto-patient

and the admin account:

devto

Password for all of them is: medidocpass@abc

I would love to hear your feedback! Let me know what you think in the comments.

MediDoc: Update 5 - Small UI Tweaks

Ayan Banerjee — Sun, 03 Jan 2021 08:25:40 +0000

In the last couple of days, I made some improvements to the UI. You can find the previous UI images in the first post.

Case card:

Now one can click on the ⭐ icon to bookmark and un-bookmark!

Comment card:

Similar to the case card, the ✏️ icon can be clicked for editing, and the trash icon can be clicked for deleting.

GitHub: https://github.com/ayan-b/MediDoc/

Check out the deployment here: https://medi-doc-njgqo.ondigitalocean.app/

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

And the patient account:

devto-patient

Password for all of them is: medidocpass@abc

Let me know what you think!

MediDoc: Update 4 - Deployment

Ayan Banerjee — Fri, 01 Jan 2021 17:59:59 +0000

Deploying Django with the Digital Ocean Apps Platform was fairly straightforward. Overall, I followed this video with some minor changes to suit my needs:

Changes I made:

If I let Django generate the secret key using get_random_secret_key() function, users have to login every time I made some code changes leading to a bad experience. Thus, I hardcode it in an environment variable.
I also have another environment variable IS_POST (default to False) which is used to control the static file hosting.
Since in MediDoc users can upload media, I also had to create DigitalOcean spaces and add the following configuration variables to my settings.py file.

if IS_PROD:
    DEFAULT_FILE_STORAGE = 'storages.backends.s3boto3.S3Boto3Storage'
    AWS_S3_REGION_NAME = 'nyc3'
    AWS_S3_ENDPOINT_URL = f'https://{AWS_S3_REGION_NAME}.digitaloceanspaces.com'
    AWS_ACCESS_KEY_ID = os.getenv('AWS_ACCESS_KEY_ID')
    AWS_SECRET_ACCESS_KEY = os.getenv('AWS_SECRET_ACCESS_KEY')
    AWS_STORAGE_BUCKET_NAME = 'medidoc'
    AWS_S3_OBJECT_PARAMETERS = {
        'CacheControl': 'max-age=86400',
    }
    AWS_LOCATION = 'media'

In the end, I have the following environment variables:

Check out the deployment here: https://medi-doc-njgqo.ondigitalocean.app/

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

And the patient account:

devto-patient

Password for all of them is: medidocpass@abc

Let me know what you think!

MediDoc: Update 3 - Admin Approval and Profile Page

Ayan Banerjee — Thu, 31 Dec 2020 18:01:51 +0000

Check out the first post to see what I am building for this hackathon!

Admin Approval

In general, admins (local authorities) approve an application for registration of a hospital, pharmacy, or diagnosis center in the platform.

Profile Page

Profile page for medical users (hospital/pharmacy/diagnosis centers). They are publicly accessible.

Stay tuned for the next update!

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

And the patient account:

devto-patient

Password for all of them is: medidocpass@abc

Let me know what you think!

MediDoc: Update 2 - Improve UI and Add User Functionality

Ayan Banerjee — Wed, 30 Dec 2020 06:59:18 +0000

Check out the previous post for an overview of the project!

UI Improvement

In my last post Szabolcs suggested focusing on the UI. Here are some changes I made following his suggestions!

Added a light grey background on the case details page. Also, files and comments are inside cards now:
Replaced the DOWNLOAD button with an icon:

Improvement in Add User Action

Added ability to remove a user.
Added autocomplete.

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

And the patient account:

devto-patient

Password for all of them is: medidocpass@abc

Let me know what you think!

Chest X-Ray photo by CDC on Unsplash

MediDoc: What Got Done Till Now

Ayan Banerjee — Mon, 28 Dec 2020 16:26:55 +0000

A couple of months ago I came across this thread by DHH:

DHH

@dhh

Going to the doctor in Denmark after living in the US for the past 15 years is surreal. There was zero paperwork! No copays. The prescription was digitally available in all pharmacies in the country immediately following the appointment. SOCIALIST BUREAUCRACY RUN AMOK 😂

14:49 PM - 04 Nov 2020

A similar thing I have also noticed here in India and a considerable amount of time is wasted on these paperwork activities! So in this hackathon, I am trying to build a web app that addresses this issue!

Introducing MediDoc: Paperless and Efficient Healthcare Management Software

Tech Stack

I am using Django in the backend and MaterializeCSS in the frontend. A superuser is required to access the admin panel.

Workflow

A typical treatment case in hospital -

Take admission in a hospital
Hospital prescribes some medicines in a paper, and the patient (or the family of the patient) has to buy it from a pharmacy
Hospital asks the patient to get some diagnosis (say, MRI, X-ray, etc.), and it is performed in a diagnosis center. The patient gets the scanning done and finally brings the result back to the hospital. S/he may have to wait quite some time in the diagnosis center to get paper-works done and get those scanning results.

So as we can see, there are quite a few manual steps in the flow of work, and in many places, paperwork is involved.

MediDoc is a web app that tries to get rid of this paperwork and thus making the whole process much more efficient.

In this web app, there are 4 types of users:

Normal user (or patient)
Hospital
Pharmacy
Diagnosis Center

Sign in as admin (superuser).
Add a new user to the page http://localhost:port_number/add-user

Admin can add different types of users - hospital, pharmacy, and diagnosis center.

We can now sign in as a hospital user. The first page is a list of recent cases. As we have signed in as a new user, we'll see an empty cases list.

We can now a case by clicking on the + button at the bottom right corner. Note that the patient must exist, otherwise we'll encounter an internal server error. We can also add media in the description box.

After adding the case we can view it, and add some comments.

Check how neatly the comments are organized. We can also upload a file and add different types of users. Again, users must exist. Add the users using the ADD USER tab below. The comments and case description can be edited as well.

Access Level: Once a user is added, they will see their kind of data only. For example, a pharmacy can see only prescription-related comments and files. In this way, they only get to see what is relevant to them. It is up to the hospital to provide relevant information to different types of users.
My Library: If we think a file will be useful later, we can add it to our library by clicking on the + button on the file. It can be accessed library by clicking on the profile icon in the top right and then clicking on the library. One can remove files from the library as well.

Mark a case as inactive: Once a case is resolved, it can be marked as inactive by clicking on the EDIT button in the description panel, and unchecking the active checkbox. The case will no longer show up on the recent cases list.
All cases: All cases can be accessed by clicking on All Cases in the navbar.

Advantages

Zero paperwork, a patient fills the required information (blood group, allergies, etc.) during sign up
No paperwork for prescriptions as well
Documents (e.g., x-ray scan) can be saved in my library and referenced later
Past case histories can be referenced for similar cases in future

Try It Out

To try it out, please create a patient account here and a medical account here (note that admin has to approve the medical accounts, so please wait a bit!).

Alternatively, you can use the following demo medical accounts:

devto-hospital
devto-diag
devto-pharmacy

And the patient account:

devto-patient

Password for all of them is: medidocpass@abc

Let me know what you think!

Cover photo by Lucas Vasques on Unsplash

Chest X-Ray photo by CDC on Unsplash

Tabifier Action - Convert Leading White spaces to Tabs

Ayan Banerjee — Tue, 08 Sep 2020 04:11:48 +0000

Want to work at Piep Piper? 👨‍💻 👩‍💻
You must use this action in all of your repository!

My Workflow

This action converts leading whitespaces in your repository to tabs. Richard Hendricks will be happy!

This action takes 1 optional input - tabLength (default value is 4 - means 4
spaces will be replaced by 1 tab. The values are always rounded up, e.g. 7
spaces will be replaced by 2 tabs). Note that, files inside .github directory
are ignored. Along with this, you also need to specify the github_token environment variable.

Here is an example workflow:

name: Tabify

on:
  push:
    branches: [ master ]

jobs:
  build:
    runs-on: ubuntu-latest
    steps:
    - name: Repo checkout
      uses: actions/checkout@v2
    - name: Tabify
      uses: ayan-b/tabifier-action@master
      env:
        github_token: ${{ secrets.GITHUB_TOKEN }}
      with:
        tabLength: 4
    - name: Commit and push
      run: |
        git status
        git add .
        git config --global user.name "github-actions[bot]"
        git config --global user.email "41898282+github-actions[bot]@users.noreply.github.com"
        git commit -m "Tabify"
        # change the link according to your repository
        git push https://ayan-b:${GITHUB_TOKEN}@github.com/ayan-b/tabifier-playground HEAD:master

Submission Category:

Wacky Wildcards

Link to Code

The action can be found in this repo:

ayan-b / tabifier-action

Tabifier Action

Want to work at Piep Piper? You must use this action in all of your repository!

This action converts leading whitespaces in your repository to tabs. Richard Hendricks will be happy!

This action takes 1 optional input - tabLength (default value is 4 - means 4 spaces will be replaced by 1 tab. The values are always rounded up, e.g. 7 spaces will be replaced by 2 tabs). Note that, files inside .github directory are ignored.

Here is an example workflow:

name: Tabify
on:
  push:
    branches: [ master ]

jobs:
  build:
    runs-on: ubuntu-latest
    steps:
    - name: Repo checkout
      uses: actions/checkout@v2
    - name: Tabify
      uses: ayan-b/tabifier-action@master
      env:
        github_token: ${{ secrets.GITHUB_TOKEN }}
      with:
        tabLength: 4
    - name: Commit and push
      run: |
        git status
        git add .
        git config --global user.name "github-actions[bot]"

…

View on GitHub

Additional Resources / Info

You can see this action in action here.

Jump responsibly!

Source

Create a LaTeX Resume and Website from a Single Data File

Ayan Banerjee — Sun, 06 Sep 2020 05:46:49 +0000

My Workflow

How about creating a site without touching HTML or creating a LaTeX resume without knowing LaTeX!? Enter resume-generator-action! 🎉

Simply fill in this data.yml file and your website and resume will be live in GitHub pages. Make sure to enable GitHub Pages in your repository. Point the publishing source to gh-pages.

More Customization: 🎨

Change the Jekyll theme in the _config.yml_jj2 file for a different look of your site
Modify the resume template and markdown template for a different layout of resume and your site respectively

Submission Category:

DIY Deployments

Yaml File or Link to Code

ayan-b / resume-generator-action

Generate your website and resume from a YAML using GitHub actions!

Resume Generator Action

How about creating a site without touching HTML or creating a LaTeX resume without knowing LaTeX!? Enter resume-generator-action!

Simply fill in this data.yml file and your website and resume will be live in GitHub pages. Make sure to enable GitHub Pages in your repository. Point the publishing source to gh-pages.

More Customization:

Change the Jekyll theme in the _config.yml_jj2 file for a different look of your site
Modify the resume template and markdown template for a different layout of resume and your site respectively

Trivia

This action was made for Actions Hackathon.

License

MIT

View on GitHub

Additional Resources / Info

Live demo: Website | Resume

This project would not have been possible without the following open source projects:

moban: for generating the tex and markdown file from template
latex-action: for compiling LaTeX and creating PDF
actions-gh-pages: for deploying to GitHub pages
sb2nov/resume: for the awesome resume design

Please let me know if you have any feedback or if you want me to add new features! Thank you!

Count Number of Substrings with Only 1s

Ayan Banerjee — Mon, 13 Jul 2020 00:00:00 +0000

Given a binary string, count no of substrings with only 1’s. Since the resulting count could be huge, print it modulo $10^9 + 7$ .

Example :

Input: “11101101”

Output: 10

Explanation: “1” occurs 6 times, “11” occurs 3 times and “111” occurs 1 time. Thus number of substrings with only 1’s = 6 + 3 + 1 = 10.

Approach: Sliding Window

Intuition

We can see that a ‘0’ divides two blocks of ‘1’s. For a block of ‘1’ with length l has $1 + 2 + 3 + ... + l = l * (l + 1) /2$ substrings. Thus, we only need to count the length of each block of 1’s and use the above formula.

For example, the string “11101101” can be divided into blocks of 1’s having 3 characters, 2 characters and 1 character which will give 3 * (3 + 1) / 2 = 6, 2 * (2 + 1) / 2 = 3 and 1 * (1 + 1) / 2 = 1 substring respectively.

Implementation

C++ code:

#include <iostream>
#include <string>
using namespace std;

int subCount(string s) {
    const int MOD = 1e9 + 7;
    int i = 0, l = s.length();
    int ans = 0;
    while (i < l) {
        int count = 0; // count gives length of block of 1's
        if (s[i] == '1') {
            while(i < l and s[i] == '1') {
                ++count;
                ++i;
            }
            long substringCount = 1L * count * (count + 1) / 2 % MOD;
            ans = (ans + substringCount) % MOD;
        } else {
            ++i;
        }
    }
    return ans;
}

int main() {
    cout << "Number of substring with only 1's for 11101101 is " << subCount("11101101") << endl;
    return 0;
}

Python code:

def sub_count(s):
    MOD = 10**9 + 7
    i = 0
    l = len(s)
    ans = 0
    while i < l:
        if s[i] == '1':
            count = 0 # count gives length of block of 1's
            while i < l and s[i] == '1':
                count += 1
                i += 1
            substring_count = count * (count + 1) // 2 % MOD
            ans = (ans + substring_count) % MOD
        else:
            i += 1
    return ans

if __name__ == ' __main__':
    print("Number of substring with only 1's for 11101101 is", sub_count('11101101'))

Complexity Analysis

Time Complexity: $O (n)$ where n is the length of string.
Space Complexity: $O (1)$ as we are not using any extra space.

Count Number of Set Bits of an Integer using Brian-Kernighan Method

Ayan Banerjee — Tue, 07 Jul 2020 02:37:41 +0000

Count the number of set bits of an integer.

Examples:

Input: 31
Output: 5
Explanation: Binary representation of 31 is 11111

Input: 42
Output: 3
Explanation: Binary representation of 42 is 101010

Approach-1: Naive

Naive algorithm is to use the binary representation of the number and count the number of set bits.

C++ code:

#include<iostream>
using namespace std;

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        count += n & 1; // check if the last bit is set
        n = n >> 1; // right shift by 1 is equivalent to division by 2
    }
    return count;
}


int main() {
    cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
    cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
    return 0;
}

Python code:

def count_set_bits(n):
    count = 0
    while n > 0:
        count += n & 1
        n = n >> 1
    return count

if __name__ == '__main__':
    print('Number of set bits of', 31, 'is', count_set_bits(31))
    print('Number of set bits of', 42, 'is', count_set_bits(42))

Time Complexity: O(logN) where N is the number
Space Complexity: O(1) as we are not using any extra space

Approach-2: Brian Kernighan Algorithm

n = n & (n - 1) clears the rightmost set bit. Let us take a look at some
examples.

n           => 101010
n - 1       => 101001
---------------------
n & (n - 1) => 101000

n is updated to 101000 now.

n           => 101000
n - 1       => 100111
---------------------
n & (n - 1) => 100000

n is updated to 100000 now.

n           => 100000
n - 1       => 011111
--------------------------
n & (n - 1) => 000000

n is now 0.

Thus, we need only 3 iterations to find the count of set bits.

C++ code:

#include<iostream>
using namespace std;

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // clear the right-most bit
        ++count;
    }
    return count;
}


int main() {
    cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
    cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
    return 0;
}

Python code:

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n - 1)  # clear the right most bit
        count += 1
    return count

if __name__ == '__main__':
    print('Number of set bits of', 31, 'is', count_set_bits(31))
    print('Number of set bits of', 42, 'is', count_set_bits(42))

Time Complexity: O(logN) when N has all of its bit set
Space Complexity: O(1) as we are not using any extra space

Maximum Value of Equation of Ones with Addition and Multiplication Operations - An Interview Problem

Ayan Banerjee — Mon, 06 Jul 2020 03:25:45 +0000

Given an integer n, find the maximum value that can be obtained usingn ones and only addition and multiplication operations. Note that, you can insert any number of valid bracket pairs.

Example:

Input: n = 12

Output: 81

Explanation: (1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) = 81

Approach: Dynamic Programming

Observe that, in order to find the answer for n = 5, we need to consider the maximum answer obtainable from the answer of 2 and 3, 1 and 4. Thus, this problem has an optimal substructure property.

                    5
        /                 \
    op(1, 4)            op(2, 3)
    /  \                /       \
    1   op(2, 2)       op(1, 1)  op(1, 2)
        /      \          / \      /  \
    op(1, 1) op(1, 1)    1   1    1   op(1, 1)
    / \        / \                    / \
   1   1      1   1                  1   1

Here, op(m, n) = max(answer for m + answer for n, answer for m * answer for n).

Clearly, from the tree above there are a lot of overlapping sub-problems. Owing to this and optimal substructure property, this problem is an ideal candidate for dynamic programming.

Bottom-up approach:

C++ code:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

long long getMaximumValue(int n) {
    vector<long long> dp(n + 1);
    // dp[i] denotes maximum value that can be obtained from i ones
    dp[0] = 0; // base case: with 0 ones answer is always 0
    dp[1] = 1; // base case: with 1 one answer is 1
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] = max({dp[i], dp[j] + dp[i - j], dp[j] * dp[i - j]});
        }
    }
    return dp[n];
}

int main() {
    cout << "n = " << 5 << " Maximum possible value " << getMaximumValue(5) << endl; // prints
    cout << "n = " << 12 << " Maximum possible value " << getMaximumValue(12) << endl; // prints "81"
    return 0;
}

Python code:

def getMaximumValue(n):
    dp = [0] * (n + 1)
    # dp[i] denotes maximum value that can be obtained from i ones
    dp[0] = 0 # base case: with 0 ones answer is always 0
    dp[1] = 1 # base case: with 1 one answer is 1
    for i in range(2, n + 1):
        for j in range(1, i // 2 + 1):
            dp[i] = max(dp[i], dp[j] + dp[i - j], dp[j] * dp[i - j])
    return dp[n]

if __name__ == ' __main__':
    print('n =', 5, 'Maximum possible value', getMaximumValue(5))
    print('n =', 12, 'Maximum possible value', getMaximumValue(12))

Time Complexity: O(n)
Space Complexity: O(n) due to storing states in dp array

Exercise: Code the top-down approach.