Maximum Ascending Subarray Sum
Problem Statement
Aapko ek positive integers ka array diya gaya hai,
nums
. Aapko maximum possible sum return karna hai ek ascending subarray kanums
mein.Definitions:
Subarray: Array ke continuous sequence of numbers.
Ascending Subarray: Ek subarray tab ascending hota hai jab uske saare elements strictly increasing order mein hon. Matlab, har
i
ke liye jahanl <= i < r
ho,nums[i] < nums[i+1]
.
Examples:
Input:
nums = [10, 20, 30, 5, 10, 50]
Output:65
Explanation:[5, 10, 50]
ek ascending subarray hai jiska maximum sum 65 hai.Input:
nums = [10, 20, 30, 40, 50]
Output:150
Explanation:[10, 20, 30, 40, 50]
ek ascending subarray hai jiska maximum sum 150 hai.Input:
nums = [12, 17, 15, 13, 10, 11, 12]
Output:33
Explanation:[10, 11, 12]
ek ascending subarray hai jiska maximum sum 33 hai.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
Maximum Ascending Subarray Sum
Single-Pass Greedy Approach: Hum ek hi baar array ko traverse karenge.
Running Sum: Hum har ascending sequence ke liye ek running sum track karenge.
Update Maximum Sum: Jaise hi hume ek new ascending sequence milti hai, hum apna running sum update karte hain aur agar wo sum maximum se zyada hai, to maximum sum bhi update karte hain.Intuition
Initialize Variables:
currentSum = nums[0] → Yeh variable current ascending subarray ka sum track karega.
maxSum = currentSum → Yeh variable maximum sum ko store karega jo encounter kiya gaya hai.
Array ko Iterate karo (O(n)):
Har element ke liye check karo:
Agar nums[i] > nums[i-1], to nums[i] ko currentSum mein add karo (ascending subarray ko extend karo).
Warna, currentSum ko nums[i] se reset karo (naya subarray start karo).
Har step ke baad, agar currentSum maxSum se bada ho, to maxSum ko update karo.
Return maxSum:
Sabhi elements process karne ke baad maxSum return karo.Approach
Time Complexity:
Traversal: Array ko ek baar traverse kar rahe hain, har element ko sirf ek baar visit karte hain.
Operations: Har element ke liye ek simple comparison aur addition/subtraction kar rahe hain, jo constant time operations hain.
Isiliye, time complexity O(n) hai, jahan n
array ke elements ka number hai.
Space Complexity:
Extra Space: Hum do extra variables use kar rahe hain:
currentSum
aurmaxSum
.No Extra Data Structures: Hum koi extra array ya data structure use nahi kar rahe, bas kuch constant space.
Solution
/**
* @param {number[]} nums
* @return {number}
*/
var maxAscendingSum = function(nums) {
// currentSum ko initialize karo, jo current ascending subarray ka sum track karega
let currentSum = nums[0], maxSum = currentSum; // maxSum ko bhi initialize karo, jo maximum sum ko store karega
// Array ko traverse karte hain
for (let i = 1; i < nums.length; i++) {
// Agar current element pichle element se bada hai
if (nums[i] > nums[i - 1]) {
currentSum += nums[i]; // Ascending subarray ko extend karo
} else {
currentSum = nums[i]; // Naya subarray start karo
}
// maxSum ko update karo agar currentSum zyada hai
maxSum = Math.max(maxSum, currentSum);
}
// Final maximum sum return karo
return maxSum;
};
Function Definition:
var maxAscendingSum = function(nums) { ... }
: Yeh functionnums
naam ke array ko parameter ke roop mein leta hai aur maximum ascending subarray ka sum return karta hai.
Variable Initialization:
let currentSum = nums[0], maxSum = currentSum;
: Pehle element kocurrentSum
aurmaxSum
mein initialize karte hain.currentSum
current ascending subarray ka sum track karega aurmaxSum
maximum sum ko track karega.
Array Traversal:
for (let i = 1; i < nums.length; i++) { ... }
: Array ke doosre element se lekar last element tak loop chalayenge.
Check Ascending Condition:
if (nums[i] > nums[i - 1]) { ... } else { ... }
: Har element ke liye check karenge ki kya woh pichle element se bada hai.if (nums[i] > nums[i - 1]) { currentSum += nums[i]; }
: Agar bada hai, tocurrentSum
mein current element ko add karenge (ascending subarray ko extend karenge).else { currentSum = nums[i]; }
: Agar bada nahi hai, tocurrentSum
ko current element se reset karenge (naya subarray start karenge).
Update Maximum Sum:
maxSum = Math.max(maxSum, currentSum);
: Har step ke baad check karenge kicurrentSum
maxSum
se bada hai ya nahi. Agar bada hai, tomaxSum
ko update karenge.
Return Result:
return maxSum;
: Loop complete hone ke baad, maximum ascending subarray ka summaxSum
return karenge.
Solution
class Solution {
public:
int maxAscendingSum(vector& nums) {
// currentSum ko initialize karo, jo current ascending subarray ka sum track karega
int currentSum = nums[0], maxSum = currentSum; // maxSum ko bhi initialize karo, jo maximum sum ko store karega
// Array ko iterate karte hain
for (int i = 1; i < nums.size(); i++) {
// Agar current element pichle element se bada hai
if (nums[i] > nums[i - 1]) {
currentSum += nums[i]; // Ascending subarray ko extend karo
} else {
currentSum = nums[i]; // Naya subarray start karo
}
// maxSum ko update karo agar currentSum zyada hai
maxSum = max(maxSum, currentSum);
}
// Final maximum sum return karo
return maxSum;
}
};
Class Declaration:
class Solution { ... };
: Yeh classSolution
ke naam se define ki gayi hai.
Function Declaration:
int maxAscendingSum(vector<int>& nums) { ... }
: Yeh functionmaxAscendingSum
ka naam hai, jo ek vectornums
ko parameter ke roop mein leta hai aur maximum ascending subarray ka sum return karta hai.
Variable Initialization:
int currentSum = nums[0], maxSum = currentSum;
: Pehle element kocurrentSum
aurmaxSum
mein initialize karte hain.currentSum
current ascending subarray ka sum track karega aurmaxSum
maximum sum ko track karega.
Array Traversal:
for (int i = 1; i < nums.size(); i++) { ... }
: Array ke doosre element se lekar last element tak loop chalayenge.
Check Ascending Condition:
if (nums[i] > nums[i - 1]) { ... } else { ... }
: Har element ke liye check karenge ki kya woh pichle element se bada hai.if (nums[i] > nums[i - 1]) { currentSum += nums[i]; }
: Agar bada hai, tocurrentSum
mein current element ko add karenge (ascending subarray ko extend karenge).else { currentSum = nums[i]; }
: Agar bada nahi hai, tocurrentSum
ko current element se reset karenge (naya subarray start karenge).
Update Maximum Sum:
maxSum = max(maxSum, currentSum);
: Har step ke baad check karenge kicurrentSum
maxSum
se bada hai ya nahi. Agar bada hai, tomaxSum
ko update karenge.
Return Result:
return maxSum;
: Loop complete hone ke baad, maximum ascending subarray ka summaxSum
return karenge.