Day 46 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

*Problem: *
https://www.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence4749/1

Max Sum Increasing Subsequence

Difficulty: Medium Accuracy: 40.02%

Given an array of positive integers arr[], find the maximum sum of a subsequence such that the elements of the subsequence form a strictly increasing sequence.
In other words, among all strictly increasing subsequences of the array, return the one with the largest possible sum.

Examples:
Input: arr[] = [1, 101, 2, 3, 100]
Output: 106
Explanation: The maximum sum of an increasing sequence is obtained from [1, 2, 3, 100].
Input: arr[] = [4, 1, 2, 3]
Output: 6
Explanation: The maximum sum of an increasing sequence is obtained from [1, 2, 3].

Input: arr[] = [4, 1, 2, 4]
Output: 7
Explanation: The maximum sum of an increasing sequence is obtained from [1, 2, 4].
Constraints:
1 ≤ arr.size() ≤ 103
1 ≤ arr[i] ≤ 105

Solution:
class Solution:
def maxSumIS(self, arr):
n = len(arr)
dp = arr[:]
for i in range(n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + arr[i])
return max(dp)