Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Solution {
- public static void main(String[] args) {
- Scanner sc=new Scanner(System.in);
- int t=sc.nextInt();
- for(int q=0;q<t;q++){
- int n=sc.nextInt();
- int a[]=new int[n];
- for(int i=0;i<n;i++)
- a[i]=sc.nextInt();
- int ans=a[0];
- int is=0,s=0,id=0;
- int dp[]=new int[n];
- dp[0]=a[0];
- for(int i=1;i<n;i++){
- dp[i]=Math.max(0,dp[i-1])+a[i];
- ans=Math.max(ans,dp[i]);
- }
- // System.out.println(ans);
- int max=Integer.MIN_VALUE,b=Integer.MIN_VALUE;
- for(int i=0;i<n;i++){
- if(max<dp[i]){
- max=dp[i];
- id=i;
- is=s;
- }
- }
- for(int i=id;i>=0;i--){
- max=max-a[i];
- is=i;
- //System.out.println(max+" ");
- if(dp[i]==a[0]||dp[i]==0){
- break;
- }
- }
- // for(int i=0;i<n;i++)
- // System.out.print(dp[i]+" ");
- // System.out.println();
- System.out.println(dp[id]+" "+is+" "+id);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement